Graph-Theoretic Algorithms, Spring 2017: Resources


Graph-Theoretic Algorithms Spring 2017 Resources

Home
Outline
Resources
Schedule
Summaries
Assignments
Project
Exams

Homepage: http://www.student.cs.uwaterloo.ca/~cs762
Important announcements will be posted to the course homepage. Please watch it regularly.
Instructor: Therese Biedl, Room DC2341, x34721,
Office hours (tentative): Monday 12-1 or by appointment.

Forum: Learn has a place where students can discuss topics, share resourecs or organize groups. This will not be monitored regularly, so do not rely on it to get answers from the instructor.
Lecture Notes: Lecture notes are available in PDF. You will need your UW userid and password to access them. Be aware that the lecture notes may not exactly correspond to what is being taught, and many chapters will not be covered in class. I am also revising them as I teach. To save trees, don't print much beyond what's needed for the next lecture or two.
Textbook: No one textbook covers all topics in this class. Some useful resources are listed below.

Graph Classes: A Survey (A. Brandstädt, V.B. Le, J.P. Spinrad), SIAM Monographs on Discrete Mathematics and Applications, SIAM, 1999.
Excellent overview of graph classes with lots of references, but no proofs.
On reserve for 3-hour loan from the Davis Centre library. call number QA166.B73.

Planar graphs: theory and algorithms (T. Nishizeki, N. Chiba), North-Holland publisher, 1988.
Decent reference for planar graphs, but a bit old.
On reserve for 3-hour loan from the Davis Centre library, call number QA1.N855 no. 140.

Planar graph drawing (T. Nishizeki, Md. S. Rahman), Lecture Notes Series on Computing, Volume 12, World Scientific, 2004.
Newer book with focus on drawing graphs, but also some background on planar graphs in general. Sadly not available from the UW libraries unless you happen to be a Guelph user.

Algorithmic Graph Theory and Perfect Graphs (M.C. Golumbic), Academic Press, New York, 1980. 2nd edition 2004.
Great reference for interval graphs and friends, but a bit out of date. (The 2nd edition is essentially the same as the 1st, except for an epilogue chapter.)
On reserve for 3-hour loan from the Davis Centre library, call number QA166.G64 2004.

H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51 (3), 255-269, 2008.
One of the (many) review articles that Bodlaender wrote about treewidth and its algorithmic applications. Some of the older articles (search for MFCS 1998, TCS 1998 or SOFSEM 2005) go more in-depth into some of these topics, but of course are more outdated.

Graph Theory, 2nd edition (R. Diestel), Springer Verlag, 2000.
Good for minor theory; also discusses planar graphs and partial k-trees.
On reserve for 3-hour loan from the UW library, call number QA166.D51413 2000.

Homepage:	http://www.student.cs.uwaterloo.ca/~cs762 Important announcements will be posted to the course homepage. Please watch it regularly.
Instructor:	Therese Biedl, Room DC2341, x34721, Office hours (tentative): Monday 12-1 or by appointment.

Forum:	Learn has a place where students can discuss topics, share resourecs or organize groups. This will not be monitored regularly, so do not rely on it to get answers from the instructor.
Lecture Notes:	Lecture notes are available in PDF. You will need your UW userid and password to access them. Be aware that the lecture notes may not exactly correspond to what is being taught, and many chapters will not be covered in class. I am also revising them as I teach. To save trees, don't print much beyond what's needed for the next lecture or two.
Textbook:	No one textbook covers all topics in this class. Some useful resources are listed below. Graph Classes: A Survey (A. Brandstädt, V.B. Le, J.P. Spinrad), SIAM Monographs on Discrete Mathematics and Applications, SIAM, 1999. Excellent overview of graph classes with lots of references, but no proofs. On reserve for 3-hour loan from the Davis Centre library. call number QA166.B73. Planar graphs: theory and algorithms (T. Nishizeki, N. Chiba), North-Holland publisher, 1988. Decent reference for planar graphs, but a bit old. On reserve for 3-hour loan from the Davis Centre library, call number QA1.N855 no. 140. Planar graph drawing (T. Nishizeki, Md. S. Rahman), Lecture Notes Series on Computing, Volume 12, World Scientific, 2004. Newer book with focus on drawing graphs, but also some background on planar graphs in general. Sadly not available from the UW libraries unless you happen to be a Guelph user. Algorithmic Graph Theory and Perfect Graphs (M.C. Golumbic), Academic Press, New York, 1980. 2nd edition 2004. Great reference for interval graphs and friends, but a bit out of date. (The 2nd edition is essentially the same as the 1st, except for an epilogue chapter.) On reserve for 3-hour loan from the Davis Centre library, call number QA166.G64 2004. H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51 (3), 255-269, 2008. One of the (many) review articles that Bodlaender wrote about treewidth and its algorithmic applications. Some of the older articles (search for MFCS 1998, TCS 1998 or SOFSEM 2005) go more in-depth into some of these topics, but of course are more outdated. Graph Theory, 2nd edition (R. Diestel), Springer Verlag, 2000. Good for minor theory; also discusses planar graphs and partial k-trees. On reserve for 3-hour loan from the UW library, call number QA166.D51413 2000.

Webmaster:

Last modified: 04/06/2017

Graph-Theoretic Algorithms Spring 2017 Resources

Graph-Theoretic Algorithms
Spring 2017
Resources