Skip navigation
  •  Inicio
  • UDC 
    • Cómo depositar
    • Políticas do RUC
    • FAQ
    • Dereitos de Autor
    • Máis información en INFOguías UDC
  • Percorrer 
    • Comunidades
    • Buscar por:
    • Data de publicación
    • Autor
    • Título
    • Materia
  • Axuda
    • español
    • Gallegan
    • English
  • Acceder
  •  Galego 
    • Español
    • Galego
    • English
  
Ver ítem 
  •   RUC
  • Facultade de Filoloxía
  • Investigación (FFIL)
  • Ver ítem
  •   RUC
  • Facultade de Filoloxía
  • Investigación (FFIL)
  • Ver ítem
JavaScript is disabled for your browser. Some features of this site may not work without it.

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

Thumbnail
Ver/abrir
Esteban_Juan_Luis_The_scaling_of_the_minimum_sum_of_edge_lengths_in_uniformly_random_trees.pdf (627.4Kb)
Use este enlace para citar
http://hdl.handle.net/2183/19279
Coleccións
  • Investigación (FFIL) [885]
Metadatos
Mostrar o rexistro completo do ítem
Título
The scaling of the minimum sum of edge lengths in uniformly random trees
Autor(es)
Esteban, Juan Luis
Ferrer-i-Cancho, Ramon
Gómez-Rodríguez, Carlos
Data
2016-06
Cita bibliográfica
Juan Luis Esteban, Ramon Ferrer-i-Cancho and Carlos Gómez-Rodríguez, The scaling of the minimum sum of edge lengths in uniformly random trees, Journal of Statistical Mechanics: Theory and Experiment, (2016):063401, 2016.
Resumo
[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 this sum is bounded above by its value in a star tree. We also show that the mean edge length grows logarithmically in optimal linear arrangements, in stark contrast to the linear growth that is expected on optimal arrangements of star trees or on random linear arrangements.
Palabras chave
Scaling laws
Minimum linear arrangement
Trees
 
Versión do editor
http://iopscience.iop.org/article/10.1088/1742-5468/2016/06/063401/meta
ISSN
1742-5468

Listar

Todo RUCComunidades e colecciónsPor data de publicaciónAutoresTítulosMateriasGrupo de InvestigaciónTitulaciónEsta colecciónPor data de publicaciónAutoresTítulosMateriasGrupo de InvestigaciónTitulación

A miña conta

AccederRexistro

Estatísticas

Ver Estatísticas de uso
Sherpa
OpenArchives
OAIster
Scholar Google
UNIVERSIDADE DA CORUÑA. Servizo de Biblioteca.    DSpace Software Copyright © 2002-2013 Duraspace - Suxestións