Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Esteban, J. L.; Ferrer-i-Cancho, R.; Gómez-Rodríguez, C.
Tipus d'activitat
Article en revista
Revista
Journal of statistical mechanics: Theory and experiment
Data de publicació
2016-06-21
Volum
2016
Número
6
Pàgina inicial
063401
DOI
https://doi.org/10.1088/1742-5468/2016/06/063401 Obrir en finestra nova
Repositori
http://arxiv.org/abs/1602.07940 Obrir en finestra nova
http://hdl.handle.net/2117/88535 Obrir en finestra nova
URL
http://iopscience.iop.org/article/10.1088/1742-5468/2016/06/063401 Obrir en finestra nova
Resum
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 ...
Citació
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.
Paraules clau
Minimum linear arrangement, Scaling laws, Trees
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
LOGPROG - Lògica i Programació

Participants

Arxius