Approximating modular decomposition is hard

DOI10.1007/978-3-030-39219-2_5MaRDI QIDQ779173zbMATH OpenOpenAlexFDO

Authors Lalla Mouatadid, Mengchuan Zou, M. A. Habib

Publication date 21 July 2020

Full work available at URL https://doi.org/10.1007/978-3-030-39219-2_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Incremental modular decomposition
• A survey of the algorithmic aspects of modular decomposition
• Efficient and practical algorithms for sequential modular decomposition
• Algorithmic aspects of a general modular decomposition theory
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures

Cited in

(2)

• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs

This page was built for publication: Approximating modular decomposition is hard

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