A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
From MaRDI portal
Publication:3605497
DOI10.1007/978-3-642-00202-1_17zbMath1211.68288OpenAlexW1530750795MaRDI QIDQ3605497
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_17
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (7)
Fully dynamic representations of interval graphs ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ The clique-separator graph for chordal graphs ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- The clique-separator graph for chordal graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithmic graph theory and perfect graphs
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The NP-completeness column: an ongoing guide
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- Topics in Intersection Graph Theory
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Fully dynamic algorithms for chordal graphs and split graphs
This page was built for publication: A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
