Approximating the minimum clique cover and other hard problems in subtree filament graphs

DOI10.1016/j.dam.2006.03.003zbMath1110.68103MaRDI QIDQ2506362

J. Mark Keil, Lorna K. Stewart

Publication date: 28 September 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.003

zbMATH Keywords

approximation algorithm; NP-complete; circle graph; clique cover; subtree filament graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

68W25: Approximation algorithms

Related Items

Minimum weight feedback vertex sets in circle graphs, Subtree filament graphs are subtree overlap graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• A simplified NP-complete satisfiability problem
• The ellipsoid method and its consequences in combinatorial optimization
• Linear time algorithms on circular-arc graphs
• Quantifiers and approximation
• The complexity of domination problems in circle graphs
• Label placement by maximum independent set in rectangles
• Efficient graph representations
• Maximum independent set and maximum clique algorithms for overlap graphs
• Fast stabbing of boxes in high dimensions
• The NP-completeness column: an ongoing guide
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• The Complexity of Coloring Circular Arcs and Chords
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• Recognition of Circle Graphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• The complexity of colouring circle graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Partially Ordered Sets