Approximation hardness of dominating set problems in bounded degree graphs
From MaRDI portal
Publication:958303
DOI10.1016/j.ic.2008.07.003zbMath1169.68037OpenAlexW2094067618MaRDI QIDQ958303
Miroslav Chlebík, Janka Chlebíková
Publication date: 3 December 2008
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-of-dominating-set-problems-in-bounded-degree-graphs(a4f3b74e-03f6-4180-a897-8cf0dd00a505).html
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (73)
Integer linear programming formulations for double roman domination problem ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Domination in some subclasses of bipartite graphs ⋮ Algorithmic results in secure total dominating sets on graphs ⋮ Subset sum problems with digraph constraints ⋮ Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ On dominating set of some subclasses of string graphs ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Approximation algorithm and hardness results for defensive domination in graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ Algorithmic Aspects of Disjunctive Domination in Graphs ⋮ Leafy spanning \(k\)-forests ⋮ Generalized threshold processes on graphs ⋮ Complexity of edge monitoring on some graph classes ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ Tight approximation bounds for dominating set on graphs of bounded arboricity ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Approximation for the minimum cost doubly resolving set problem ⋮ Complexity of total outer-connected domination problem in graphs ⋮ Fault-tolerant total domination via submodular function approximation ⋮ Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem ⋮ Complexity results on cosecure domination in graphs ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ Complexity of total dominator coloring in graphs ⋮ Domination and convexity problems in the target set selection model ⋮ On the complexity of co-secure dominating set problem ⋮ Algorithm and hardness results on neighborhood total domination in graphs ⋮ Greed is good for deterministic scale-free networks ⋮ The complexity of secure domination problem in graphs ⋮ New techniques for approximating optimal substructure problems in power-law graphs ⋮ Approximation complexity of metric dimension problem ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ Unnamed Item ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ Independent dominating set problem revisited ⋮ Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ On Approximation Complexity of Metric Dimension Problem ⋮ On directed covering and domination problems ⋮ Tropical dominating sets in vertex-coloured graphs ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Hardness results of global total \(k\)-domination problem in graphs ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Algorithmic aspects of \(b\)-disjunctive domination in graphs ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Secure total domination in graphs: bounds and complexity ⋮ b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results ⋮ Differentiating-total domination: approximation and hardness results ⋮ On the complexity of the minimum outer-connected dominating set problem in graphs ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ On Directed Covering and Domination Problems ⋮ CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS ⋮ Algorithmic aspects of total Roman {3}-domination in graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- On approximating the minimum independent dominating set
- A short note on the approximability of the maximum leaves spanning tree problem
- On the approximability of the maximum induced matching problem
- Complexity of approximating bounded variants of optimization problems
- Approximation hardness of edge dominating set problems
- A threshold of ln n for approximating set cover
- The importance of being biased
- A new multilayered PCP and the hardness of hypergraph vertex cover
- Bipartite Domination and Simultaneous Matroid Covers
- Approximation algorithms for connected dominating sets
- Non-approximability results for optimization problems on bounded degree instances
- Some optimal inapproximability results
This page was built for publication: Approximation hardness of dominating set problems in bounded degree graphs
