Algorithms – ESA 2004

DOI10.1007/B100428MaRDI 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

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

(36)

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

This page was built for publication: Algorithms – ESA 2004

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