Name
Abstract | ||
|---|---|---|
Graph colorability (COL) is a constraint satisfaction problem, which has been studied in the context of computational complexity
and combinatorial search algorithms. It is also interesting as subjects of heuristics[2]. Many research reports discuss the
complexity of COL [2,3,4,8,9,10]. Examples of possible candidates of order parameters that explain the mechanism making COLs
very hard include the 3-paths[10], the minimal unsolvable subproblems[8], and the frozen developments[4]. Instead of generate-and-test
approaches, we propose a constructive approach producing 3-colorablity problems (3COLs) that are exceptionally hard for usual
backtracking algorithms adopting Brélaz heuristics and for Smallk coloring program[1]. Instances generated by our procedure
(1) are 4-critical, (2) include no near-4-cliques(n4c’s; 4-cliques with 1 edge removed) as subgraphs, and (3) have the degree
of every node limited to 3 or 4: quasi-regular.
|
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-45193-8_78 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
computational complexity,graph coloring,col,constraint satisfaction problem,search algorithm | Christian ministry,Computer science,Constructive,Heuristics,Backtracking,Distributed computing,Discrete mathematics,Graph,Mathematical optimization,Context of computational complexity,Algorithm,Constraint satisfaction problem,Combinatorial search | Conference |
Volume | ISSN | Citations |
2833 | 0302-9743 | 2 |
PageRank | References | Authors |
0.41 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Seiichi Nishihara | 1 | 71 | 14.35 |
| Kazunori Mizuno | 2 | 42 | 10.55 |
| Kohsuke Nishihara | 3 | 2 | 0.41 |