Synapse
⌘+K
Synapse
PulseExploreClubsResearchersJournals
Instagram
HomeClubsExplore
August 21, 2025Open Access

A Heuristics for Graph Coloring Based on the Ising Model

View Full Paper
Ask AI
Bookmark
Share

Authors

OBOmkar BihaniJŽJanez ŽerovnikUniversity of Ljubljana

Discussion

Loading...

Member takes

Implication

Dynamic algorithm estimates chromatic number in graphs, suggesting robust near-optimal solutions.

Key Points

  • The algorithm provides near-optimal solutions for graph coloring, showcasing robust performance in varied instances.
  • Evaluation reveals effectiveness on real-world graphs from the DIMACS benchmark suite and adaptability to different initialization strategies.
  • The approach employs a dynamic extension of the Petford-Welsh coloring algorithm based on the Ising model, working without a predefined k.
  • Highlighting its inherent parallelism, the randomized algorithm indicates promising potential for future exploration in complex cases.

Cite This Study

Bihani et al. (2025) studied this question.

synapsesocial.com/papers/68af55d1ad7bf08b1eadc3cfhttps://doi.org/10.20944/preprints202508.1583.v1
View Full Paper
Ask AI
Bookmark
Share

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

  1. 1A Heuristic for Graph Coloring Based on the Ising Model2025
  2. 2Experimental Analysis of Algorithms for the Dynamic Graph Coloring Problem2024 · 1 citations
  3. 3Influence of the graph density on approximate algorithms for the graph vertex coloring problem2025
  4. 4A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs2025
  5. 5A Memetic Algorithm Designed for Solving Graph Coloring Problems: A Round-Robin Sports Scheduling Case Study2024