Constructive generation of very hard 3-colorability instances

DOI10.1016/j.dam.2006.07.015zbMath1130.05058OpenAlexW2000872069MaRDI QIDQ2467358

Seiichi Nishihara, Kazunori Mizuno

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

zbMATH Keywords

heuristicsphase transitiongraph coloringNP-completesearchconstraint satisfactionhard problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Regular pattern-free coloring ⋮ Proper colorability of segment intersection graphs ⋮ Low degree Nullstellensatz certificates for 3-colorability ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ An incremental search heuristic for coloring vertices of a graph

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

This page was built for publication: Constructive generation of very hard 3-colorability instances