Web site: http://www.csie.ntu.edu.tw/~kmchao/tree05spr

In this course, we will focus on algorithms for spanning trees. Some related topics will also be covered.

Prerequisites: Some basic knowledge on algorithm development is required. Background in approximation algorithms is welcome but not required for taking this course.

Outlines:
1. Counting spanning trees
2. Minimum spanning trees
3. Shortest-paths tree
4. Minimum routing cost spanning trees
5. Communication spanning trees
6. Optimal product-requirement communication spanning trees
7. Optimal sum-requirement communication spanning trees
8. Light approximate shortest-paths trees
9. Light approximate routing cost spanning trees
10. Steiner minimal trees
11. Trees and diameters
12. Other advanced topics

References:
1. Class notes
2. Related journal and conference papers
3. Spanning Trees and Optimization Problems, by Bang Ye Wu and Kun-Mao Chao (2004), Chapman & Hall/CRC Press, USA.

Coursework:
Midterm exam (45%)
Oral presentation of selected topics or papers (40%)
Homework and class participation (15%)