Stochastic Learning for SAT- Encoded Graph Coloring Problems

View Sample PDF

Author(s): Noureddine Bouhmala (Vestfold University College, Norway)and Ole-Christoffer Granmo (University of Agder, Norway)
Copyright: 2012
Pages: 20
Source title: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends
Source Author(s)/Editor(s): Peng-Yeng Yin (Ming Chuan University, Taiwan)
DOI: 10.4018/978-1-4666-0270-0.ch017

Keywords: Algorithms / Artificial Intelligence / Computer Science & IT / Information Science Reference

Purchase

View Stochastic Learning for SAT- Encoded Graph Coloring Problems on the publisher's website for pricing and purchasing information.

Abstract

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.

The IRMA Community

Research IRM

Stochastic Learning for SAT- Encoded Graph Coloring Problems

Purchase

Abstract

Related Content

IRMA Sponsors