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

Coloring random graphs and maximizing local diversity.

S Bounkong1, J van Mourik, D Saad

  • 1Neural Computing Research Group, Aston University, Birmingham B4 7ET, United Kingdom.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|February 7, 2007
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

Artificial Intelligence Clustering Approach for Force Mapping Analysis of Polyacrylic Acid (PAA)/Polyethylene Oxide (PEO) Polymer Brushes for Biosensor Applications.

Journal of molecular recognition : JMR·2026
Same author

Communication networks beyond the capacity crunch.

Philosophical transactions. Series A, Mathematical, physical, and engineering sciences·2016
Same author

Disseminated histoplasmosis in allogeneic bone marrow transplant: a diagnosis not to be missed.

Transplant infectious disease : an official journal of the Transplantation Society·2014
Same author

Four-quadrant optical matrix-vector multiplication machine as a neural-network processor.

Applied optics·2010
Same author

Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach.

Physical review. E, Statistical, nonlinear, and soft matter physics·2008
Same author

Typical behavior of relays in communication channels.

Physical review. E, Statistical, nonlinear, and soft matter physics·2008
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 explores graph coloring on random networks, adapting belief propagation and Walksat algorithms to maximize vertex color diversity. Researchers identified critical connectivity for perfect solutions, relevant to distributed storage.

Area of Science:

  • Graph theory and network science
  • Computational complexity and algorithms

Background:

  • The graph coloring problem is fundamental in computer science and operations research.
  • Random graphs with finite average connectivity present unique challenges for algorithmic solutions.

Purpose of the Study:

  • To investigate a variation of the graph coloring problem on random graphs.
  • To adapt and evaluate efficient algorithms for maximizing color diversity among neighboring vertices.
  • To identify critical connectivity thresholds for achieving optimal solutions.

Main Methods:

  • Adaptation of belief propagation and Walksat algorithms for the graph coloring variation.
  • Experimental evaluation on two types of random graphs with varying system sizes.
  • Analysis of algorithm performance and identification of critical connectivity values.

Related Experiment Videos

Main Results:

  • Demonstrated the effectiveness of adapted belief propagation and Walksat algorithms.
  • Identified a critical connectivity value essential for algorithms to find perfect solutions.
  • Showcased the scalability and performance of the algorithms across different system sizes.

Conclusions:

  • The adapted algorithms are efficient for solving this graph coloring variation on random graphs.
  • The identified critical connectivity is a key factor for successful problem resolution.
  • The problem and algorithms have practical implications for applications like distributed storage.