Algorithms for NP-Hard Problems (Section 21.2: Color Coding) [Part 1 of 2]
Tim Roughgarden Lectures · 28:30
This lecture (Algorithms Illuminated Part 4, §21.2) shows why a TSP-style DP for the minimum-cost *k*-path problem is no faster than brute force, then develops color coding: randomly partition vertices into *k* colors...