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

Jean-Philippe Hamiez, Jin-Kao Hao and Fred W. Glover
Additional contact information
Jean-Philippe Hamiez: Université d’Angers/LERIA, France
Jin-Kao Hao: Université d’Angers, France
Fred W. Glover: OptTek Systems Inc., USA

International Journal of Applied Metaheuristic Computing (IJAMC), 2010, vol. 1, issue 4, 1-24

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.

Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 4018/jamc.2010100101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:1:y:2010:i:4:p:1-24

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().