Backtrack: An O(1) expected time algorithm for the graph coloring problem
From MaRDI portal
Publication:794430
DOI10.1016/0020-0190(84)90013-9zbMath0541.68020OpenAlexW2018663595MaRDI QIDQ794430
Publication date: 1984
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(84)90013-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (25)
Counting dominating sets and related structures in graphs ⋮ On independent sets in random graphs ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ Some corollaries of a theorem of Whitney on the chromatic polynomial ⋮ Efficient bounds on a branch and bound algorithm for graph colouration ⋮ Average-case intractability vs. worst-case intractability ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ No NP problems averaging over ranking of distributions are harder ⋮ The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Average circuit depth and average communication complexity ⋮ Maximizing proper colorings on graphs ⋮ An Extremal Property of Turán Graphs, II ⋮ Extremal Graphs for Homomorphisms II ⋮ Accelerating backtrack search with a best-first-search strategy ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Extremal graphs for homomorphisms ⋮ The maximum number of colorings of graphs of given order and size: a survey ⋮ Maximum number of colourings: 4-chromatic graphs ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ Deciding \(k\)-colorability in expected polynomial time ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ Counting colorings of a regular graph
Cites Work
This page was built for publication: Backtrack: An O(1) expected time algorithm for the graph coloring problem
