Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
From MaRDI portal
Publication:6180640
DOI10.1016/j.dam.2023.09.034zbMath1529.05131arXiv2211.16854MaRDI QIDQ6180640
Publication date: 2 January 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2211.16854
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The cluster deletion problem for cographs
- A survey of the algorithmic aspects of modular decomposition
- Complexity and parameterized algorithms for cograph editing
- Approximating modular decomposition is hard
- Weakly triangulated graphs
- Completely separable graphs
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
- Primitivity is hereditary for 2-structures
- A new characterization of HH-free graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- On a conjecture of Meyniel
- Murky graphs
- On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
- Complement reducible graphs
- On a unique tree representation for \(P_ 4\)-extendible graphs
- A tree representation for \(P_ 4\)-sparse graphs
- Recovering symbolically dated, rooted trees from symbolic ultrametrics
- Modular decomposition and transitive orientation
- Indecomposable graphs
- Minimal indecomposable graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- Beyond representing orthology relations by trees
- Distance-hereditary comparability graphs
- Reconstructing gene trees from Fitch's xenology relation
- Algorithmic graph theory and perfect graphs
- Orthology relations, symbolic ultrametrics, and cographs
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- Twin-width and generalized coloring numbers
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Best match graphs and reconciliation of gene trees with species trees
- On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- On a property of the class of n-colorable graphs
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- Representation of a finite graph by a set of intervals on the real line
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- On Comparability and Permutation Graphs
- On brittle graphs
- Dacey Graphs
- Graph Classes: A Survey
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- P-Components and the Homogeneous Decomposition of Graphs
- Twin-width I: Tractable FO Model Checking
- Transitiv orientierbare Graphen
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
- Algorithmische Graphentheorie
- Twin-width IV: ordered graphs and matrices
