6533b7d6fe1ef96bd1266537

RESEARCH PRODUCT

Solving Graph Coloring Problems Using Learning Automata

Ole-christopher GranmoNoureddine Bouhmala

subject

Theoretical computer scienceLearning automataEncoding (memory)Frequency assignmentCombinatorial optimizationGraph coloringSolverBoolean satisfiability problemMathematicsRegister allocation

description

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem with numerous applications, including time tabling, frequency assignment, and register allocation. The growing need for more efficient algorithms has led to the development of several GCP solvers. In this paper, we introduce the first GCP solver that is based on Learning Automata (LA). We enhance traditional Random Walk with LA-based learning capability, encoding the GCP as a Boolean satisfiability problem (SAT). Extensive experiments demonstrate that the LA significantly improve the performance of RW, thus laying the foundation for novel LA-based solutions to the GCP.

yearjournalcountryeditionlanguage
2008-01-01
https://doi.org/10.1007/978-3-540-78604-7_24