Ad hoc algorithms

Part 6 of the course, volume 6 of the lecture notes: chapters 41–42.

Ad hoc algorithms: the branch-and-bound on the critical item for the 0/1 knapsack problem and the DSATUR branch-and-bound for vertex coloring.

Lecture notes (PDF) Exercises (PDF)

Knapsack problems

• 41. Knapsack: branch-and-bound on the critical item

  ---

  The algorithm for the KP · A worked example

  Read the chapter · Exercises

Coloring problems

• 42. Vertex coloring: the DSATUR branch-and-bound

  ---

  The algorithm for the VCP · A worked example

  Read the chapter · Exercises