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

DOI10.1016/S0166-218X(03)00448-7MaRDI QIDQ1427188zbMATH OpenFDO

Authors Ron Shamir, Roded Sharan

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) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Graph-Theoretic Concepts in Computer Science
• Fully dynamic recognition algorithm and certificate for directed cographs
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 6472575 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Graph Classes: A Survey
• Incremental modular decomposition
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The splittance of a graph
• Threshold graphs and related topics
• Trivially perfect graphs

Cited in

(22)

• Graph-Theoretic Concepts in Computer Science
• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
• Characterizing and computing minimal cograph completions
• On dynamic threshold graphs and related classes
• Fully dynamic recognition of proper circular-arc graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• A fully dynamic algorithm for recognizing and representing chordal graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Strong triadic closure in cographs and graphs of low maximum degree
• Fully dynamically maintaining minimal integral separator for threshold and difference graphs
• Fully dynamic representations of interval graphs
• A fully dynamic algorithm for the recognition of P₄-sparse graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Dynamically maintaining split graphs
• A survey of the algorithmic aspects of modular decomposition
• Graph-Theoretic Concepts in Computer Science
• Linear-time algorithm for the matched-domination problem in cographs
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Fully dynamic representations of interval graphs

This page was built for publication: A fully dynamic algorithm for modular decomposition and recognition of cographs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1427188)