2007/02/21 by David Aldous, Aldous, David
Engineering · Environmental Science · Physics and Astronomy · Social Sciences · #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #Traffic control and management #Transportation Planning and Optimization #Urban Transport and Accessibility #Wildlife-Road Interactions and Conservation #cond-mat.stat-mech
paper · pdf · doi:10.48550/arxiv.cond-mat/0702502
arxiv created 2007/02/21 · openalex publication_date 2007/02/21 · arxiv updated 2009/12/01 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Consider networks on n vertices at average density 1 per unit area. We seek a network that minimizes total length subject to some constraint on journey times, averaged over source-destination pairs. Suppose journey times depend on both route-length and number of hops. Then for the constraint corresponding to an average of 3 hops, the length of the optimal network scales as n13/10. Alternatively, constraining the average number of hops to be 2 forces the network length to grow slightly faster than order n3/2. Finally, if we require the network length to be O(n) then the mean number of hops grows as order log log n. Each result is an upper bound in the worst case (of vertex positions), and a lower bound under randomness or equidistribution assumptions. The upper bounds arise in simple hub and spoke models, which are therefore optimal in an order of magnitude sense.