Method
backtracking
Articles
GRA
Algorithm
Graph colouring
Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables.
O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap
2 problems
PAR
Technique
Backtracking
Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings.
O(bᵈ) in the worst case
2 problems
PAR
Technique
Branch and bound
38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242.
exponential in the worst case
1 problem
Problems
Often together
classic 3 graph 2 heuristic 2 coloring 2 greedy 1 scheduling 1 maps and navigation 1 compilers 1 recursion 1 satisfiability 1 games 1 interviews 1