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

DOI10.1016/0020-0190(84)90013-9zbMATH Open0541.68020OpenAlexW2018663595MaRDI QIDQ794430FDOQ794430

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

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

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)

Cites Work

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

Cited In (30)

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

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)