Lecture Notes
Week 15: Random selection and random orientation
T
Week 14: Indirect Certificating
M,
T
Week 13: Random separation
M,
(2020)L1,
L2,
L3,
L4
Week 12: Random partition and random separation
M,
T
Week 11: Color coding
M,
T
Week 10: Iterative compression
M,
T
Week 9: Parameterized intractability: W[1]-hardness
M,
M2,
T
Week 8: Kernelization
M,
T
Week 7: FPT algorithms -- bounded search tree
M,
T
Week 6: Proving NP-completeness
M,
T
Week 5: Network flows
Week 4: Matching
M,
T
Week 3: All-pairs shortest paths
M1,
M2,
T
Week 2: Minimum spanning trees
Week 1: Introduction -- graph problems from applications
--------------------------------------------------------------------
The
Chinese University of Hong Kong
