A fully dynamic algorithm for the recognition of P₄-sparse graphs

DOI10.1016/J.TCS.2012.03.020MaRDI QIDQ441871zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

modular decompositionrecognition\(P_{4}\)-sparse graphfully dynamic algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42) Graph representations (geometric and intersection representations, etc.) (05C62)

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₄-reducible and extended P₄-sparse graphs

Cites work

• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Recognition Algorithm for Cographs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A tree representation for \(P_ 4\)-sparse graphs
• A vertex incremental approach for maintaining chordality
• 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
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Fully dynamic representations of interval graphs
• Graph Classes: A Survey
• Incremental modular decomposition
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Modular decomposition and transitive orientation
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

Cited in

(6)

• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Fully dynamic recognition of proper circular-arc graphs
• Fully dynamic representations of interval graphs
• A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
• scientific article; zbMATH DE number 4206028 (Why is no real title available?)

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)