From modular decomposition trees to rooted median graphs

DOI10.1016/J.DAM.2021.12.017MaRDI QIDQ2074346zbMATH OpenOpenAlexFDO

Authors Carmen Bruckmann, Peter F. Stadler, Marc Hellmuth

Publication date 9 February 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

\(2\)-structuresalgorithmhalf-gridhypercubeMedian graphmodular decompositionprime moduleprime vertex replacementsymbolic ultrametrics

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory (05C90)

Abstract: The modular decomposition of a symmetric map $deltacolonXimesXoUpsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrmlca(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by "extended" hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting "tree-like" median graphs may be of use in phylogenetics as a model of evolutionary relationships.

Recommendations

• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• A survey of the algorithmic aspects of modular decomposition
• Incremental modular decomposition
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• Unifying Two Graph Decompositions with Modular Decomposition

Cites work

• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• A canonical decomposition theory for metrics on a finite set
• A general algorithmic scheme for modular decompositions of hypergraphs and applications
• A note on the tree realizability of a distance matrix
• A survey of the algorithmic aspects of modular decomposition
• Alternative characterizations of Fitch's xenology relation
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• An Algorithm for the Modular Decomposition of Hypergraphs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Cograph editing: Merging modules is equivalent to editing P₄s
• Combinatorics and geometry of finite and infinite squaregraphs
• Complement reducible graphs
• Daisy cubes and distance cube polynomial
• Daisy cubes: a characterization and a generalization
• Fully dynamic recognition algorithm and certificate for directed cographs
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• scientific article; zbMATH DE number 1339499 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Incremental construction of 2-structures
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• On median graphs and median grid graphs
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
• On the number of vertices and edges of the Buneman graph
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Orthology relations, symbolic ultrametrics, and cographs
• Pairwise compatibility graphs: a survey
• Primitivity is hereditary for 2-structures
• Reconstructing gene trees from Fitch's xenology relation
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• The relation graph
• The structure of median graphs
• Theory of 2-structures
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Transitiv orientierbare Graphen

Cited in

(10)

• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Planar median graphs and cubesquare-graphs
• Arboreal structure and regular graphs of median-like classes
• Injective split systems
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Shared ancestry graphs and symbolic arboreal maps
• Arboreal networks and their underlying trees
• Representing distance-hereditary graphs with multi-rooted trees
• On a generalization of median graphs: k-median graphs
• Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints

This page was built for publication: From modular decomposition trees to rooted median graphs

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