Course: Special topics on graph algorithms
Spring semester, 2008
Thursday 9:10 - 12:10, 111 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree08spr
Instructor: Kun-Mao Chao (趙坤茂)
TA: 羅正偉 (臺大資訊工程研究所博士生)
Prerequisites: Some basic
knowledge on algorithm development is required. Background in approximation
algorithms is welcome but not required for taking this course.
Coursework:
Two midterm exams (35% each; tentatively on 4/10/2008 & 5/15/2008)
Oral presentation of selected topics or papers (20%)
Homework and class participation (10%)
Our classmates: I II III (An-Chiang is taking photos for us.) IV V (Treewe by AC)
Last class: I (Wetree) II III IV V VI
Class notes:
A note on a 2-approximation algorithm for the MRCT problem
A note on 15/8 & 3/2-approximation algorithms for the MRCT problem
A note on a polynomial time approximation scheme for the MRCT problem (More details)
Optimal Communication Spanning Trees
A 2-approximation algorithm for the SROCT problem
A note on eccentricities, diameters, and
radii
A note on the uniform edge-partition of a
tree
Slides:
Homework:
Class presentations:
1. Suggested number of team members: about 6
2. Each member is required to present in turn;
3. Revised slides should be sent to me one week after the presentation;
4. Questions in class are always welcome;
Selected papers for presentation:
2008/5/22
V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18:263–270, 1997.
黃于鳴 林振慶 曾照涵 廖鳳玉 張瀠文 陳冠宇
2008/5/29
D. R. Karger, P. N. Klein, and R. E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42:321–328, 1995.
張紘睿 蘇承祖 戴宇晉 許智程 黃則翰
2008/6/5
Martin Fürer, Balaji Raghavachari: Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree. SODA 1992: 317-324
林佳慶 楊鈞羽 陳建霖 郭慶徵 宋彥朋
2008/6/12
Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003: 448-455. (Its journal version appeared in JCSS, 2004.)
朱安強 呂維倫 湯志賢 吳韋霖 林晏禕 高孟駿
Alternative options:
M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46:362–394, 1999.
References (not required):
1. Spanning Trees and Optimization Problems, by Bang Ye Wu and Kun-Mao Chao (2004), Chapman & Hall/CRC Press, USA.
2. Related journal and conference papers
Useful Links:
Special topics on graph algorithms, Spring 2004
Special topics on graph algorithms, Spring 2005
Special topics on graph algorithms, Spring 2006
Special topics on graph algorithms, Spring 2007
Handbook on Approximation Algorithms and Metaheuristics (edited by Prof. Teo Gonzalez)
