Graph-Theoretic Algorithms Spring 2024 Resources

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

Instructor:	Therese Biedl, Room DC2341, Office hours (tentative): Wednesday after class 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. We will otherwise not be using LEARN and you do not need to visit it ever.
Lecture Notes:	Lecture notes are available in PDF. You must be registered in CS762 (or have contactd the instructor) to access them, and need to log in with your UW userid and password. The PDF will be watermarked with your name; please do not share it. 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. If you repeatedly cannot access them from the library without putting a hold on them, then please contact me (I can have them put on 3-hour loan reserve, but in the past that was not necessary). 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. Available from the WLU 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. Available from the UW 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. Somewhat 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.) Available from the UW library, call number (1st ed.) QA166.G64 1980 and (2nd ed.) 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. Available from the UW library, call number QA166.D51413 2000.