Constructive generation of very hard 3-colorability instances
From MaRDI portal
Publication:2467358
DOI10.1016/j.dam.2006.07.015zbMath1130.05058MaRDI QIDQ2467358
Kazunori Mizuno, Seiichi Nishihara
Publication date: 21 January 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.015
heuristics; phase transition; graph coloring; NP-complete; search; constraint satisfaction; hard problem
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency in networks of relations
- Local optima topology for the \(k\)-coloring problem
- The hardest constraint problems: A double phase transition
- Exploiting the deep structure of constraint problems
- New methods to color the vertices of a graph
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Frozen development in graph coloring