The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest common ancestor of x and y in T, i.e., if δ(x,y)=t(lca(x,y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive 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 δ.
%0 Journal Article
%1 bruckmann2022modular
%A Bruckmann, Carmen
%A Stadler, Peter F.
%A Hellmuth, Marc
%D 2022
%J Discrete Applied Mathematics
%K 2-structures Algorithm Half-grid Hypercube Median_graph Modular_decomposition Prime_module Prime_vertex_replacement Symbolic_ultrametrics
%P 1--9
%R https://doi.org/10.1016/j.dam.2021.12.017
%T From modular decomposition trees to rooted median graphs
%U https://www.sciencedirect.com/science/article/pii/S0166218X21005035
%V 310
%X The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest common ancestor of x and y in T, i.e., if δ(x,y)=t(lca(x,y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive 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 δ.
@article{bruckmann2022modular,
abstract = {The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest common ancestor of x and y in T, i.e., if δ(x,y)=t(lca(x,y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive 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 δ.},
added-at = {2024-10-02T13:52:45.000+0200},
author = {Bruckmann, Carmen and Stadler, Peter F. and Hellmuth, Marc},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/25972ae0dd548b3c6d467b4926a2c6b58/scadsfct},
doi = {https://doi.org/10.1016/j.dam.2021.12.017},
interhash = {5cfd110d98fa04e9ad83a0be70429de0},
intrahash = {5972ae0dd548b3c6d467b4926a2c6b58},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
keywords = {2-structures Algorithm Half-grid Hypercube Median_graph Modular_decomposition Prime_module Prime_vertex_replacement Symbolic_ultrametrics},
pages = {1--9},
timestamp = {2024-10-02T13:52:45.000+0200},
title = {From modular decomposition trees to rooted median graphs},
url = {https://www.sciencedirect.com/science/article/pii/S0166218X21005035},
volume = 310,
year = 2022
}
