APX-hardness of domination problems in circle graphs

DOI10.1016/j.ipl.2005.11.007zbMath1181.68157OpenAlexW2010667653MaRDI QIDQ1045943

Sriram V. Pemmaraju, Mirela Damian

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

computational complexitydominating setAPX-hardnesscircle graph

Mathematics Subject Classification ID

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) Approximation algorithms (68W25)

Related Items (4)

On dominating set of some subclasses of string graphs ⋮ Two heuristic solution concepts for the vehicle selection problem in line haul transports ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of domination problems in circle graphs
• Probabilistic checking of proofs
• The Complexity of Coloring Circular Arcs and Chords
• Topics in Intersection Graph Theory
• Recognition of Circle Graphs
• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• Recognizing circle graphs in polynomial time
• The complexity of theorem-proving procedures
• Algorithms for a maximum clique and a maximum independent set of a circle graph

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