Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Minimum spanning trees and random resistor networks in d dimensions.

N Read1

  • 1Department of Physics, Yale University, P.O. Box 208120, New Haven, Connecticut 06520-8120, USA.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 26, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Proof of Single-Replica Equivalence in Short-Range Spin Glasses.

Physical review letters·2023
Same author

Complexity as information in spin-glass Gibbs states and metastates: Upper bounds at nonzero temperature and long-range models.

Physical review. E·2022
Same author

Nontrivial maturation metastate-average state in a one-dimensional long-range Ising spin glass: Above and below the upper critical range.

Physical review. E·2021
Same author

Delay in diagnosis of patients with head-and-neck cancer in Canada: impact of patient and provider delay.

Current oncology (Toronto, Ont.)·2020
Same author

One-step replica-symmetry-breaking phase below the de Almeida-Thouless line in low-dimensional spin glasses.

Physical review. E·2020
Same author

Multicritical Point on the de Almeida-Thouless Line in Spin Glasses in d>6 Dimensions.

Physical review letters·2018

Minimum spanning trees in d dimensions exhibit universal scaling behavior. Their properties are closely linked to percolation theory, with exponents matching critical phenomena in various dimensions.

Area of Science:

  • Statistical physics
  • Graph theory
  • Computational geometry

Background:

  • Minimum spanning trees (MSTs) are fundamental in network analysis.
  • Understanding their behavior in different dimensions and under varying conditions is crucial.
  • Previous research has explored MSTs in specific models, but a unified understanding of their scaling properties is lacking.

Purpose of the Study:

  • To investigate the universal scaling behavior of minimum-cost spanning trees in d-dimensional lattice and Euclidean models.
  • To establish relationships between MST properties and critical exponents from percolation theory.
  • To explore the implications for related problems like the Steiner tree and traveling salesman problems.

Main Methods:

  • Analysis of optimal tree costs in d-dimensional boxes with corrections of order L(theta).

Related Experiment Videos

  • Investigation of crossover phenomena at non-zero temperatures using a crossover length xi.
  • Application of Kruskal's greedy algorithm and its connection to percolation and random resistor networks.
  • Scaling analysis of entropy and free energy at small non-zero temperatures.

    • Main Results:

    • A universal d-dependent exponent theta characterizes cost corrections in MSTs.
    • A scaling relation theta = -1/nu is established, linking MSTs to percolation.
    • The correlation length exponent for ordinary percolation, nu(perc), is shown to equal nu and -1/theta in all dimensions d >= 1.
    • Crossover behavior at non-zero temperatures is described by a crossover length xi ~ T(-nu).

    Conclusions:

    • MSTs share universality classes with percolation, Steiner trees, and the traveling salesman problem (in 2D).
    • The findings provide a unified framework for understanding these network problems across different dimensions.
    • The study highlights the deep connections between graph algorithms, statistical physics, and critical phenomena.