ترغب بنشر مسار تعليمي؟ اضغط هنا

From Modular Decomposition Trees to Rooted Median Graphs

84   0   0.0 ( 0 )
 نشر من قبل Marc Hellmuth
 تاريخ النشر 2021
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

The modular decomposition of a symmetric map $deltacolon Xtimes 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.

قيم البحث

اقرأ أيضاً

We introduce some natural families of distributions on rooted binary ranked plane trees with a view toward unifying ideas from various fields, including macroevolution, epidemiology, computational group theory, search algorithms and other fields. In the process we introduce the notions of split-exchangeability and plane-invariance of a general Markov splitting model in order to readily obtain probabilities over various equivalence classes of trees that arise in statistics, phylogenetics, epidemiology and group theory.
124 - Lorenzo Ciardo 2021
The Perron value $rho(T)$ of a rooted tree $T$ has a central role in the study of the algebraic connectivity and characteristic set, and it can be considered a weight of spectral nature for $T$. A different, combinatorial weight notion for $T$ - the moment $mu(T)$ - emerges from the analysis of Kemenys constant in the context of random walks on graphs. In the present work, we compare these two weight concepts showing that $mu(T)$ is almost an upper bound for $rho(T)$ and the ratio $mu(T)/rho(T)$ is unbounded but at most linear in the order of $T$. To achieve these primary goals, we introduce two new objects associated with $T$ - the Perron entropy and the neckbottle matrix - and we investigate how different operations on the set of rooted trees affect the Perron value and the moment.
124 - Akihiro Munemasa , Yoshio Sano , 2014
In this paper, we study the characteristic polynomials of the line graphs of generalized Bethe trees. We give an infinite family of such graphs sharing the same smallest eigenvalue. Our family generalizes the family of coronas of complete graphs discovered by Cvetkovic and Stevanovic.
Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. We first consider this prob lem for trees and prove that the minimum bisection width of every tree $T$ on $n$ vertices satisfies $MinBis(T) leq 8 n Delta(T) / diam(T)$. Second, we generalize this to arbitrary graphs with a given tree decomposition $(T,X)$ and give an upper bound on the minimum bisection width that depends on the structure of $(T,X)$. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
Let $T_{n}$ be the set of rooted labeled trees on $set{0,...,n}$. A maximal decreasing subtree of a rooted labeled tree is defined by the maximal subtree from the root with all edges being decreasing. In this paper, we study a new refinement $T_{n,k} $ of $T_n$, which is the set of rooted labeled trees whose maximal decreasing subtree has $k+1$ vertices.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا