From modular decomposition trees to rooted median graphs

Bruckmann, Carmen (author)

Stadler, Peter F. (author)

(creator_code:org_t)

Elsevier BV, 2022
2022
English.
In: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 310, s. 1-9

Related links:: https://doi.org/10.1...; show more...; https://doi.org/10.1...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

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 δ.

By the author/editor: Bruckmann, Carme ...; Stadler, Peter F ...; Hellmuth, Marc

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Discrete Mathema ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.