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

Polynomial iterative algorithms for coloring and analyzing random graphs.

A Braunstein1, R Mulet, A Pagnani

  • 1International Center for Theoretical Physics, Strada Costiera 11, P.O. Box 586, I-34100 Trieste, Italy.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 4, 2003
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

Evolutionary emergent metabolic interactions in cell cultures: A statistical mechanics point of view.

Physical review. E·2025
Same author

Author Correction: Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Structure of the space of folding protein sequences defined by large language models.

Physical biology·2024
Same author

Native state of natural proteins optimizes local entropy.

Physical review. E·2022
Same author

From random point processes to hierarchical cavity master equations for stochastic dynamics of disordered systems in random graphs: Ising models and epidemics.

Physical review. E·2021
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

This study analyzes graph coloring on random graphs, finding that low connectivity allows coloring while high connectivity makes it impossible. A new algorithm efficiently colors graphs in a challenging but solvable phase.

Area of Science:

  • Computational complexity theory
  • Statistical physics
  • Graph theory

Background:

  • The graph coloring problem is a fundamental problem in computer science and mathematics.
  • Understanding the behavior of graph coloring on random graphs is crucial for theoretical and practical applications.
  • Previous research has explored the phase transitions in random graph coloring but lacked precise characterization of certain regions.

Purpose of the Study:

  • To determine the critical average connectivity for graph colorability in random graphs with a fixed number of colors.
  • To investigate the existence and properties of a clustering phase in the hard-to-color but still colorable region.
  • To develop an efficient algorithm for coloring random graphs within this specific challenging regime.

Main Methods:

Related Experiment Videos

  • Analysis of the graph coloring problem on random graphs with finite average connectivity (c).
  • Application of a one-step replica-symmetry breaking approximation to find critical average connectivity (c(q)).
  • Extension of the analysis to single graph instances to ensure robustness of results.

Main Results:

  • Identified a sharp threshold for colorability: graphs with low connectivity are colorable, while high connectivity graphs are uncolorable.
  • Determined the precise value of critical average connectivity c(q) using replica-symmetry breaking.
  • Discovered a clustering phase for average connectivity c in [c(d), c(q)], characterized by an exponential number of ground state clusters.
  • Developed a polynomial-time algorithm effective for coloring random graphs in the identified hard-but-colorable region.

Conclusions:

  • The study provides a comprehensive understanding of the phase transitions in random graph coloring.
  • The identified clustering phase offers new insights into the structure of ground states in difficult instances.
  • The proposed algorithm offers a practical solution for coloring challenging random graphs, bridging theory and application.