Presentation 2003/5/22
Toward Systematic Generation of EHIs for Graph 3-Colorability
Kazunori MIZUNO, Seiichi NISHIHARA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Graph colorability, COL, is a typical constraint satisfaction problem to which phase transition phenomena, PTs, are important in the computational complexity of combinatorial search algorithms. Secondary PT, rather than primary PT, is significant and sutle because it claims that, in the secondary PT region, exceptionally hard instances (EHIs) are found that may require exponential-order computational time to solve. To clarify the PT mechamism, many studies have been undertaken to produce very hard instances, many of which were based on generate-and-test approaches. We propose a rather systematic or constructive algorithm that repeats the embedding of 4-critical graphs to arbitrarily generate large extraordinarily hard 3COL instances. We demonstrate experimentally that the computational cost of our 3COL instances is of an exponential order of the number of vertices by using a few actual coloring algorithms.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) graph coloring / search / phase transition / NP-complete / hard problem / heuristics
Paper # AI2003-1
Date of Issue

Conference Information
Committee AI
Conference Date 2003/5/22(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Artificial Intelligence and Knowledge-Based Processing (AI)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Toward Systematic Generation of EHIs for Graph 3-Colorability
Sub Title (in English)
Keyword(1) graph coloring
Keyword(2) search
Keyword(3) phase transition
Keyword(4) NP-complete
Keyword(5) hard problem
Keyword(6) heuristics
1st Author's Name Kazunori MIZUNO
1st Author's Affiliation Institute of Information Sciences and Electronics, University of Tsukuba()
2nd Author's Name Seiichi NISHIHARA
2nd Author's Affiliation Institute of Information Sciences and Electronics, University of Tsukuba
Date 2003/5/22
Paper # AI2003-1
Volume (vol) vol.103
Number (no) 103
Page pp.pp.-
#Pages 6
Date of Issue