A theoretical analysis of backtracking in the graph coloring problem

DOI10.1016/0196-6774(85)90044-6zbMath0601.68039OpenAlexW2043243657MaRDI QIDQ3736910

Edward A. Bender, Herbert S. Wilf

Publication date: 1985

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(85)90044-6

zbMATH Keywords

NP-completeaverage behaviorrun time distribution

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)

Related Items (16)

Some corollaries of a theorem of Whitney on the chromatic polynomial ⋮ Efficient bounds on a branch and bound algorithm for graph colouration ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Multi-scale process modelling and distributed computation for spatial data ⋮ Maximizing proper colorings on graphs ⋮ An Extremal Property of Turán Graphs, II ⋮ Accelerating backtrack search with a best-first-search strategy ⋮ The maximum number of colorings of graphs of given order and size: a survey ⋮ Maximum number of colourings: 4-chromatic graphs ⋮ Deciding \(k\)-colorability in expected polynomial time ⋮ A network-flow-based lower bound for the minimum weighted integer coloring problem ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ Counting colorings of a regular graph

This page was built for publication: A theoretical analysis of backtracking in the graph coloring problem