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

DOI10.1016/j.dam.2006.03.003zbMath1110.68103OpenAlexW2076513440MaRDI 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 algorithmNP-completecircle graphclique coversubtree filament graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (12)

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ Subtree filament graphs are subtree overlap graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Max point-tolerance graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Parameterized domination in circle graphs ⋮ Minimum weight feedback vertex sets in circle graphs ⋮ Unnamed Item ⋮ Generalised online colouring problems in overlap graphs ⋮ On the chromatic number of disjointness graphs of curves ⋮ Revising Johnson's table for the 21st century

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

This page was built for publication: Approximating the minimum clique cover and other hard problems in subtree filament graphs