Loading...
Loading...

Go to the content (press return)

The scaling of the minimum sum of edge lengths in uniformly random trees

Author
Esteban, J. L.; Ferrer-i-Cancho, R.; Gómez-Rodríguez, C.
Type of activity
Journal article
Journal
Journal of statistical mechanics: Theory and experiment
Date of publication
2016-06-21
Volume
2016
Number
6, article 063401
First page
1
Last page
18
DOI
https://doi.org/10.1088/1742-5468/2016/06/063401 Open in new window
Repository
http://arxiv.org/abs/1602.07940 Open in new window
http://hdl.handle.net/2117/88535 Open in new window
URL
http://iopscience.iop.org/article/10.1088/1742-5468/2016/06/063401 Open in new window
Abstract
The minimum linear arrangement problem on a network consists of finding the minimum sum of edge lengths that can be achieved when the vertices are arranged linearly. Although there are algorithms to solve this problem on trees in polynomial time, they have remained theoretical and have not been implemented in practical contexts to our knowledge. Here we use one of those algorithms to investigate the growth of this sum as a function of the size of the tree in uniformly random trees. We show that ...
Citation
Esteban, J., Ferrer-i-Cancho, R., Gómez-Rodríguez, C. The scaling of the minimum sum of edge lengths in uniformly random trees. "Journal of statistical mechanics: Theory and experiment", 21 Juny 2016, vol. 2016, núm. 6, article 063401, p.1-18.
Keywords
Minimum linear arrangement, Scaling laws, Trees
Group of research
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability
LOGPROG - Logic and Programming

Participants

Attachments