Backtrack: An O(1) expected time algorithm for the graph coloring problem

DOI10.1016/0020-0190(84)90013-9MaRDI QIDQ794430zbMATHOpenAlexFDO

Authors Herbert S. Wilf

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

zbMATH Keywords

graph coloringaverage complexitybacktrack algorithm

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)

Recommendations

• A theoretical analysis of backtracking in the graph coloring problem
• Average-case complexity of backtrack search for coloring sparse random graphs
• Principles and Practice of Constraint Programming – CP 2004
• Deciding \(k\)-colorability in expected polynomial time
• scientific article; zbMATH DE number 1962838

Cites work

• Coloured Graphs: A Correction and Extension
• Counting Coloured Graphs
• The Number of k-Coloured Graphs on Labelled Nodes

Cited in

(29)

• The maximum number of colorings of graphs of given order and size: a survey
• A hard problem that is almost always easy
• Counting dominating sets and related structures in graphs
• A theoretical analysis of backtracking in the graph coloring problem
• Some properties of sets tractable under every polynomial-time computable distribution
• An expected polynomial time algorithm for coloring 2-colorable 3-graphs
• Average-case complexity of backtrack search for coloring sparse random graphs
• Graph theory (algorithmic, algebraic, and metric problems)
• Maximum number of colourings: 4-chromatic graphs
• Some corollaries of a theorem of Whitney on the chromatic polynomial
• Complexity of coloring random graphs: an experimental study of the hardest region
• Accelerating backtrack search with a best-first-search strategy
• Efficient bounds on a branch and bound algorithm for graph colouration
• Extremal graphs for homomorphisms. II
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• Deciding \(k\)-colorability in expected polynomial time
• Principles and Practice of Constraint Programming – CP 2004
• An Extremal Property of Turán Graphs, II
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• Counting colorings of a regular graph
• Maximizing proper colorings on graphs
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings
• Average circuit depth and average communication complexity
• Average-case intractability vs. worst-case intractability
• No NP problems averaging over ranking of distributions are harder
• Extremal graphs for homomorphisms
• A proof of Tomescu's graph coloring conjecture
• The resolution complexity of random graph \(k\)-colorability

This page was built for publication: Backtrack: An O(1) expected time algorithm for the graph coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794430)