Approximation hardness of dominating set problems

DOI10.1007/978-3-540-30140-0_19MaRDI QIDQ5464578zbMATH OpenOpenAlexFDO

Authors Miroslav Chlebík, Janka Chlebíková

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100428

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation hardness of dominating set problems in bounded degree graphs
• Approximation hardness of edge dominating set problems
• Algorithms and Computation
• Approximating theDomatic Number
• On approximating the minimum independent dominating set

Cited in

(37)

• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• The parameterized complexity of the induced matching problem
• APX-hardness of domination problems in circle graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• The k-hop connected dominating set problem: approximation and hardness
• On directed covering and domination problems
• On the approximability of positive influence dominating set in social networks
• On the complexity of independent dominating set with obligations in graphs
• An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity
• Dual domination problems in graphs
• A polynomial-time approximation to a minimum dominating set in a graph
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• The complexity of dissociation set problems in graphs
• New kernels for several problems on planar graphs
• Approximation hardness of edge dominating set problems
• Hardness of fully dense problems
• On the complexity landscape of the domination chain
• Upper domination: complexity and approximation
• The complexity and approximability of minimum contamination problems
• Approximating the domatic number
• A decidability result for the dominating set problem
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• The constant inapproximability of the parameterized dominating set problem
• scientific article; zbMATH DE number 2172821 (Why is no real title available?)
• Inapproximability of dominating set on power law graphs
• Approximating theDomatic Number
• On directed covering and domination problems
• Algorithms and Computation
• On the Parameterized Complexity of Approximating Dominating Set
• Domination in Geometric Intersection Graphs
• Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes
• Approximation Algorithms and Hardness for Domination with Propagation
• On approximating the minimum independent dominating set
• Approximability results for the maximum and minimum maximal induced matching problems
• Approximation hardness of dominating set problems in bounded degree graphs
• The hub number of a graph

This page was built for publication: Approximation hardness of dominating set problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5464578)