From modular decomposition trees to rooted median graphs

DOI10.1016/j.dam.2021.12.017zbMath1482.05038arXiv2103.06683OpenAlexW4206554908MaRDI QIDQ2074346

Marc Hellmuth, Carmen Bruckmann, Peter F. Stadler

Publication date: 9 February 2022

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

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

zbMATH Keywords

algorithmhypercubemodular decompositionhalf-gridMedian graphprime module\(2\)-structuresprime vertex replacementsymbolic ultrametrics

Mathematics Subject Classification ID

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

Related Items (3)

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Injective split systems ⋮ Planar median graphs and cubesquare-graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• 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
• Complement reducible graphs
• A canonical decomposition theory for metrics on a finite set
• The structure of median graphs
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• On the number of vertices and edges of the Buneman graph
• Incremental construction of 2-structures
• The relation graph
• On median graphs and median grid graphs
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• 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
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Daisy cubes: a characterization and a generalization
• A general algorithmic scheme for modular decompositions of hypergraphs and applications
• Daisy cubes and distance cube polynomial
• Alternative characterizations of Fitch's xenology relation
• Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
• Fully dynamic recognition algorithm and certificate for directed cographs
• Combinatorics and Geometry of Finite and Infinite Squaregraphs
• Pairwise Compatibility Graphs: A Survey
• On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• 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
• Theory of 2-structures
• Cograph editing: Merging modules is equivalent to editing P_4s
• Transitiv orientierbare Graphen
• A note on the tree realizability of a distance matrix

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