APX-hardness of domination problems in circle graphs

DOI10.1016/J.IPL.2005.11.007MaRDI QIDQ1045943zbMATH OpenOpenAlexFDO

Authors Mirela Damian, Sriram Pemmaraju

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.11.007

zbMATH Keywords

APX-hardnesscircle graphcomputational complexitydominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1522921
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 1445364
• Parameterized domination in circle graphs
• The complexity of domination problems in circle graphs

Cites work

• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Approximation algorithms for NP-hard problems.
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Probabilistic checking of proofs
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• The Complexity of Coloring Circular Arcs and Chords
• The complexity of domination problems in circle graphs
• The complexity of theorem-proving procedures
• Topics in Intersection Graph Theory

Cited in

(9)

• The complexity of domination problems in circle graphs
• On dominating set of some subclasses of string graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Two heuristic solution concepts for the vehicle selection problem in line haul transports
• scientific article; zbMATH DE number 1522921 (Why is no real title available?)
• Approximating dominating set on intersection graphs of rectangles and L-frames
• A survey on variant domination problems in geometric intersection graphs
• Minimum selective subset on unit disk graphs and circle graphs
• Complexity classes for online problems with and without predictions

This page was built for publication: APX-hardness of domination problems in circle graphs

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