From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats

DOI10.1016/j.dam.2022.06.042zbMath1497.05218arXiv2112.05537OpenAlexW4284966016WikidataQ114191413 ScholiaQ114191413MaRDI QIDQ2172401

G. E. Scholz, Marc Hellmuth

Publication date: 15 September 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.05537

zbMATH Keywords

cographsrecognition algorithmsmodular decompositionphylogenetic networksprime modulesgalled treeprime vertex replacement

Mathematics Subject Classification ID

Problems related to evolution (92D15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cluster deletion problem for cographs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A survey of the algorithmic aspects of modular decomposition
• Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
• On the minimum sum coloring of \(P_4\)-sparse 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
• On the X-join decomposition for undirected graphs
• Complement reducible graphs
• A canonical decomposition theory for metrics on a finite set
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• On the number of vertices and edges of the Buneman graph
• Modular decomposition and transitive orientation
• The relation graph
• Indecomposable graphs
• Minimal indecomposable graphs
• Graphs indecomposable with respect to the X-join
• On variations of \(P_{4}\)-sparse graphs
• Reconstructing unrooted phylogenetic trees from symbolic ternary metrics
• Beyond representing orthology relations by trees
• A simple linear time algorithm for cograph recognition
• Reconstructing gene trees from Fitch's xenology relation
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• Orthology relations, symbolic ultrametrics, and cographs
• Upper bounds to the clique width of graphs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Indirect identification of horizontal gene transfer
• From modular decomposition trees to rooted median graphs
• Three-way symbolic tree-maps and ultrametrics
• A lower bound on the tree-width of graphs with irrelevant vertices
• Alternative characterizations of Fitch's xenology relation
• 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
• Encoding and constructing 1-nested phylogenetic networks with trinets
• On a property of the class of n-colorable graphs
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Phylogeny
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Dacey Graphs
• Graphs with unique maximal clumpings
• Graph Classes: A Survey
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• The Pathwidth and Treewidth of Cographs
• Cograph editing: Merging modules is equivalent to editing P_4s
• A short note on undirected Fitch graphs
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Orthology Relation and Gene Tree Correction: Complexity Results
• Algorithm Theory - SWAT 2004
• Transitiv orientierbare Graphen
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

This page was built for publication: From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats