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

DOI10.1007/11917496_23zbMATH Open1167.05337OpenAlexW1861154958MaRDI QIDQ3522962FDOQ3522962

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

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
• Graph-Theoretic Concepts in Computer Science
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

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)

Cited In (5)

• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Title not available (Why is that?)

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)