Minimum spanning trees and random resistor networks in d dimensions

Details Minimum spanning trees and random resistor networks in d dimensions Minimum spanning trees and random resistor networks in d dimensions

2005-04-11

arxiv.org/abs/cond-mat/0504268v2

Phys. Rev. E 72, 036114 (2005)

Physics

Condensed Matter

Statistical Mechanics

19 pages. v2: minor changes in introduction, extra reference

Scientific paper

10.1103/PhysRevE.72.036114

We consider minimum-cost spanning trees, both in lattice and Euclidean models, in d dimensions. For the cost of the optimum tree in a box of size L, we show that there is a correction of order L^theta, where theta < 0 is a universal d-dependent exponent. There is a similar form for the change in optimum cost under a change in boundary condition. At non-zero temperature T, there is a crossover length xi approx equal to T^{-nu}, such that on length scales larger than xi, the behavior becomes that of uniform spanning trees. There is a scaling relation theta=-1/nu, and we provide several arguments that show that nu and -1/theta both equal nu_perc, the correlation length exponent for ordinary percolation in the same dimension d, in all dimensions d > 1. 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 non-zero T, 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 theta=-3/4 in two dimensions.

Affiliated with

Also associated with

No associations

Rating

Minimum spanning trees and random resistor networks in d dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum spanning trees and random resistor networks in d dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum spanning trees and random resistor networks in d dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350017