A fully dynamic algorithm for modular decomposition and recognition of cographs.

DOI10.1016/S0166-218X(03)00448-7zbMath1062.68092MaRDI QIDQ1427188

Roded Sharan, Ron Shamir

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

RecognitionModular decompositionCographFully dynamic algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ On dynamic threshold graphs and related classes ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Fully dynamic representations of interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Fully dynamic recognition algorithm and certificate for directed cographs ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Fully dynamic recognition of proper circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• The splittance of a graph
• Trivially perfect graphs
• Threshold graphs and related topics
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• Graph Classes: A Survey
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs