Bounds of the sum of edge lengths in linear arrangements of trees
A fundamental problem in network science is the normalization of the topological or physical distance between vertices, that requires understanding the range of variation of the unnormalized distances. Here we investigate the limits of the variation of the physical distance in linear arrangements of the vertices of trees. In particular, we investigate various problems on the sum of edge lengths in trees of a fixed size: the minimum and the maximum value of the sum for specific trees, the minimum and the maximum in classes of trees (bistar trees and caterpillar trees) and finally the minimum and the maximum for any tree. We establish some foundations for research on optimality scores for spatial networks in one dimension.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Maximum Linear Arrangement Problem for trees under projectivity and planarity
A linear arrangement is a mapping $\pi$ from the $n$ vertices of a graph $G$ to $n$ distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the ed…
The expected sum of edge lengths in planar linearizations of trees. Theory and applications
Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. Th…
SentenceMinimum projective linearizations of trees in linear time
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping $\pi$ from vertices of a graph to distinct integers that minimizes $\sum_{\{u,v\}\in E}|\pi(u) - \pi(v)|$. In that setting, vertices are often as…
Species Trees Forcing Parsimony to Fail
To the known fact that Parsimony method sometimes fails on the problem of inferring species trees from gene trees, here we proved that no mater of what topology the true 9-taxon and greater species tree is the only thing…
Finding high posterior density phylogenies by systematically extending a directed acyclic graph
Bayesian phylogenetics typically estimates a posterior distribution, or aspects thereof, using Markov chain Monte Carlo methods. These methods integrate over tree space by applying local rearrangements to move a tree thr…