Minimum spanning trees and random resistor networks inddimensions
Author:
- 14 September 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 72 (3) , 036114
Abstract
We consider minimum-cost spanning trees, both in lattice and Euclidean models, in dimensions. For the cost of the optimum tree in a box of size , we show that there is a correction of order , where is a universal -dependent exponent. There is a similar form for the change in optimum cost under a change in boundary condition. At nonzero temperature , there is a crossover length , such that on length scales larger than , the behavior becomes that of uniform spanning trees. There is a scaling relation , and we provide several arguments that show that and both equal , the correlation length exponent for ordinary percolation in the same dimension , in all dimensions . The arguments all rely on the close relation of Kruskal’s greedy algorithm for the minimum spanning tree, percolation, and (for some arguments) random resistor networks. The scaling of the entropy and free energy at small nonzero , and hence of the number of near-optimal solutions, is also discussed. We suggest that the Steiner tree problem is in the same universality class as the minimum spanning tree in all dimensions, as is the traveling salesman problem in two dimensions. Hence all will have the same value of in two dimensions.
Keywords
All Related Versions
This publication has 60 references indexed in Scilit:
- Traveling Salesman Problem, Conformal Invariance, and Dense PolymersPhysical Review Letters, 2004
- Dense Loops, Supersymmetry, and Goldstone Phases in Two DimensionsPhysical Review Letters, 2003
- Invasion Percolation and Global OptimizationPhysical Review Letters, 1996
- Spin-glass model with dimension-dependent ground state multiplicityPhysical Review Letters, 1994
- Directed paths in a random potentialPhysical Review B, 1991
- The Cavity Method and the Travelling-Salesman ProblemEurophysics Letters, 1989
- On the solution of the random link matching problemsJournal de Physique, 1987
- Scaling theory of Ising spin glassesJournal of Physics C: Solid State Physics, 1984
- Lower critical dimension of Ising spin glasses: a numerical studyJournal of Physics C: Solid State Physics, 1984
- A note on two problems in connexion with graphsNumerische Mathematik, 1959