Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs

DOI10.1007/978-3-031-49190-0_8MaRDI QIDQ6591462

Marc Hellmuth, G. E. Scholz

Publication date: 22 August 2024

zbMATH Keywords

modular decompositionlinear-time algorithmsNP-hard problemscographperfect ordergalled-tree

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A survey of the algorithmic aspects of modular decomposition
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• On the complexity of recognizing perfectly orderable graphs
• Complement reducible graphs
• Modular decomposition and transitive orientation
• Beyond representing orthology relations by trees
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Efficient and practical algorithms for sequential modular decomposition
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• A Linear Recognition Algorithm for Cographs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Algorithmische Graphentheorie

Related Items (1)

The weighted total cophenetic index: a novel balance index for phylogenetic networks

This page was built for publication: Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs

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