A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs

DOI10.1007/11917496_23MaRDI QIDQ3522962zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_23

zbMATH Keywords

modular decompositionrecognitionfully dynamic algorithms\(P_{4}\)-sparse graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A fully dynamic algorithm for the recognition of P₄-sparse graphs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph-Theoretic Concepts in Computer Science
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

Cited in

(5)

• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• Fully dynamic algorithm for recognition and modular decomposition of permutation 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?)
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques

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 Q3522962)