| 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 | |