From Modular Decomposition Trees to Rooted Median Graphs

The modular decomposition of a symmetric map \(\delta\colon X\times X \to \Upsilon\) (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 expla...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-03
Main Authors: Bruckmann, Carmen, Stadler, Peter F, Hellmuth, Marc
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Colon
Decomposition
Graph coloring
Graphs
Hypercubes
Trees
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The modular decomposition of a symmetric map \(\delta\colon X\times X \to \Upsilon\) (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(\mathrm{lca}(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.
ISSN:2331-8422