Bounds of the sum of edge lengths in linear arrangements of trees
arXiv:2006.14069 · doi:10.1088/1742-5468/abd4d7
Abstract
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.
arXiv commentTitle changed at proof stage
References in corpus (15)
- Efficient Behavior of Small-World Networks
- Economic Small-World Behavior in Weighted Networks
- Epidemic spreading in complex networks with degree correlations
- The risks of mixing dependency lengths from sequences of different length
- The placement of the head that minimizes online memory: a complex systems approach
- Are crossing dependencies really scarce?
- Anti dependency distance minimization in short sequences. A graph theoretic approach
- Non-crossing dependencies: least effort, not grammar
- Hubiness, length, crossings and their relationships in dependency trees
- Memory limitations are hidden in grammar
- The scaling of the minimum sum of edge lengths in uniformly random trees
- Sizing the length of complex networks
- The sum of edge lengths in random linear arrangements
- A correction on Shiloach's algorithm for minimum linear arrangement of trees
- Edge crossings in random linear arrangements