A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs

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

zbMATH Keywords

recognitionmodular decomposition\(P_{4}\)-sparse graphfully dynamic algorithm

Mathematics Subject Classification ID

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