The
Chinese University of Hong Kong
Lecture
T9-11 (SHB 503)
Announcements
2009.11.20 Assignment 3 posted
2009.10.22 Assignment 2 posted
2009.9.30 Assignment 1 posted
2009.9.9 Homepage released.
Lecture Notes
Papers: Iterative Compression,
Color Coding,
Random Separation
Lecturer
Prof. Cai Leizhen
Grading Scheme
Homework (40%), Quiz (10%) and Course Project (50%)
Course
Description
A course on graph theory and graph algorithms with emphasis on the algorithmic aspects of graph theory. The course will cover classical topics such as search techniques, connectivity, colouring, matching and covering, network flows, planarity, traversability, perfect graphs, and NP-completeness of graph problems. It will also cover recent advances in graph minors and fixed-parameter tractability of graph problems. Prerequisite: CSC3160 or its equivalent.
Graph Algorithms = Graph Theory + Algorithmics + Data Structures
This term we will mainly focus on FPT algorithms and discuss the following techniques for designing such algorithms: bounded search tree, kernelization, colour coding of Alon, Yuster and Zwick, iterative compression of Reed, Smith and Vetta, and random separation of Cai, Chan and Chan.
Reference Books
- J. Kleinberg and E. Tardos, Algorithm Design, Pearson, 2006.
- R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
- R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford Press, 2006.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
- D.B. West, Introduction to Graph Theory, Pretice Hall, 1996.
Related Journals
- Graph Theory
J. of Combinatorial Theory (B) (JCTB), Combinatorica, J. of Graph Theory (JGT), Discrete Math., Graphs and Combinatorics. - Graph Theory and Algorithms
SIAM J. on Discrete Math., Discrete Applied Math. (DAM), Networks.
- Algorithms
SIAM J. on Computing, J. of Algorithms, Algorithmica, Information Processing Letters (IPL).
