A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition

View Sample PDF

Author(s): Jean-Philippe Hamiez (Université d’Angers/LERIA, France), Jin-Kao Hao (Université d’Angers, France)and Fred W. Glover (OptTek Systems Inc., USA)
Copyright: 2012
Pages: 28
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.ch012

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

Purchase

View A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition on the publisher's website for pricing and purchasing information.

Abstract

The authors present an experimental investigation of tabu search (TS) to solve the 3-coloring problem (3-COL). Computational results reveal that a basic TS algorithm is able to find proper 3-colorings for random 3-colorable graphs with up to 11000 vertices and beyond when instances follow the uniform or equipartite well-known models, and up to 1500 vertices for the hardest class of flat graphs. This study also validates and reinforces some existing phase transition thresholds for 3-COL.

The IRMA Community

Research IRM

A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition

Purchase

Abstract

Related Content

IRMA Sponsors