Name
Abstract | ||
|---|---|---|
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. PTs are significant and subtle because, in the PT region, extraordinarily hard problem instances are found, which may require exponential-order computational time to solve. To clarify PT mechanism, 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 3-colorability instances. We demonstrated experimentally that the computational cost to solve our generated instances is of an exponential order of the number of vertices by using a few actual coloring algorithms and constraint satisfaction algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2006.07.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
search,np-complete,heuristics,constraint satisfaction algorithm,3-colorability instance,typical constraint satisfaction problem,hard problem,exponential-order computational time,constructive generation,pt region,hard instance,pt mechanism,constraint satisfaction,phase transition,computational cost,graph coloring,hard problem instance,computational complexity,np complete,col,search algorithm,constraint satisfaction problem | Constraint satisfaction,Combinatorics,Search algorithm,Constructive,Algorithm,Constraint satisfaction problem,Combinatorial search,Mathematics,Critical graph,Computational complexity theory,Graph coloring | Journal |
Volume | Issue | ISSN |
156 | 2 | Discrete Applied Mathematics |
Citations | PageRank | References |
15 | 0.87 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazunori Mizuno | 1 | 42 | 10.55 |
| Seiichi Nishihara | 2 | 71 | 14.35 |