Approximating modular decomposition is hard

DOI10.1007/978-3-030-39219-2_5zbMATH Open1453.68133OpenAlexW3000817392MaRDI QIDQ779173FDOQ779173

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

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

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)

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)