Maximum independent set and maximum clique algorithms for overlap graphs
From MaRDI portal
Publication:1408815
DOI10.1016/S0166-218X(02)00418-3zbMath1022.05081MaRDI QIDQ1408815
Publication date: 25 September 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
Subtree filament graphs are subtree overlap graphs ⋮ On simultaneous planar graph embeddings ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ How to guard a graph? ⋮ 3D-interval-filament graphs ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Minimum vertex cover in rectangle graphs ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs
Cites Work
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Characterizing intersection classes of graphs
- A study on two geometric location problems
- The max clique problem in classes of string-graphs
- Arbres et dimension des ordres
- Covering and coloring polygon-circle graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Polynomial time algorithms on circular-arc overlap graphs
- Containment Graphs, Posets, and Related Classes of Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- On rectangle intersection and overlap graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Partially Ordered Sets
- Sur deux propriétés des classes d'ensembles
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Maximum independent set and maximum clique algorithms for overlap graphs