Parameterized approximation algorithms for some location problems in graphs

DOI10.1007/978-3-319-71147-8_24zbMath1474.90254arXiv1706.07475OpenAlexW3123320605WikidataQ129499668 ScholiaQ129499668MaRDI QIDQ5915898

Feodor F. Dragan, Arne Leitert

Publication date: 26 March 2018

Published in: Theoretical Computer Science, Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.07475

zbMATH Keywords

graph algorithmsconnected \(p\)-centertree-lengthconnected \(r\)-dominationlayering partitiontree-breadth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (4)

Parameterised counting in logspace ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation hardness of dominating set problems in bounded degree graphs
• Clustering to minimize the maximum intercluster distance
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Approximation algorithms for connected dominating sets
• A note on distance approximating trees in graphs
• Fast approximation algorithms for \(p\)-centers in large \(\delta \)-hyperbolic graphs
• Spanners for bounded tree-length graphs
• Completeness in approximation classes beyond APX
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Optimal dynamic program for r-domination problems over tree decompositions
• Algorithms – ESA 2005
• Parameterized approximation algorithms for some location problems in graphs

This page was built for publication: Parameterized approximation algorithms for some location problems in graphs