A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
From MaRDI portal
Publication:441871
DOI10.1016/j.tcs.2012.03.020zbMath1246.05152OpenAlexW2038728469MaRDI QIDQ441871
Stavros D. Nikolopoulos, Charis Papadopoulos, Leonidas Palios
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.020
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Density (toughness, etc.) (05C42)
Related Items (3)
Fully dynamic representations of interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- A vertex incremental approach for maintaining chordality
- Dynamically maintaining split graphs
- A tree representation for \(P_ 4\)-sparse graphs
- Modular decomposition and transitive orientation
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- Fully dynamic recognition algorithm and certificate for directed cographs
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Fully dynamic algorithms for chordal graphs and split graphs
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Fully Dynamic Representations of Interval Graphs
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
This page was built for publication: A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
