Efficient and Practical Algorithms for Sequential Modular Decomposition

DOI10.1006/jagm.2001.1185zbMath1017.68154OpenAlexW2052388845MaRDI QIDQ2775895

Elias Dahlhaus, Jens Gustedt, Ross M. McConnell

Publication date: 8 July 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/73b726fec2cb2625f5e07ef147b2d13be901e263

zbMATH Keywords

modular decomposition

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (32)

Minimal separators in \(P_4\)-sparse graphs ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ On transitive orientations with restricted covering graphs ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization. ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ An efficient exact algorithm for triangle listing in large graphs ⋮ Matching cutsets in graphs of diameter 2 ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times ⋮ On the structure of (\(P_{5}\),\,gem)-free graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ Linear-time modular decomposition of directed graphs ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Applying modular decomposition to parameterized cluster editing problems ⋮ Graphs of linear clique-width at most 3 ⋮ Structure and stability number of chair-, co-P- and gem-free graphs revisited ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ The possible cardinalities of global secure sets in cographs ⋮ Probe threshold and probe trivially perfect graphs ⋮ On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: Efficient and Practical Algorithms for Sequential Modular Decomposition