A fully dynamic algorithm for the recognition of P₄-sparse graphs
DOI10.1016/J.TCS.2012.03.020zbMATH Open1246.05152OpenAlexW2038728469MaRDI QIDQ441871FDOQ441871
Authors: Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos 
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
Recommendations
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Graph Classes: A Survey
- Modular decomposition and transitive orientation
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- A tree representation for \(P_ 4\)-sparse graphs
- Title not available (Why is that?)
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- Fully dynamic recognition algorithm and certificate for directed cographs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- Fully dynamic representations of interval graphs
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
- A vertex incremental approach for maintaining chordality
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Dynamically maintaining split graphs
- Efficient and practical algorithms for sequential modular decomposition
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Fully dynamic algorithms for chordal graphs and split graphs
Cited In (6)
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- Fully dynamic recognition of proper circular-arc graphs
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
- Title not available (Why is that?)
- Fully dynamic representations of interval graphs
This page was built for publication: A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441871)
