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

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

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

average complexitybacktrack algorithmgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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)

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

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)