Monte Carlo Graph Coloring
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916673969192960 |
|---|---|
| author | Cazenave, Tristan Negrevergne, Benjamin Sikora, Florian |
| author_facet | Cazenave, Tristan Negrevergne, Benjamin Sikora, Florian |
| contents | Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03277 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monte Carlo Graph Coloring Cazenave, Tristan Negrevergne, Benjamin Sikora, Florian Artificial Intelligence Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones. |
| title | Monte Carlo Graph Coloring |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2504.03277 |