Course: Special topics on graph algorithms
Spring semester, 2004
Thursday 14:20 – 17:20, 409 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree04spr
Instructor: Kun-Mao Chao (趙坤茂)
Prerequisites: Some basic
knowledge on algorithm development is required. Background in approximation
algorithms is welcome but not required for taking this course.
****** Notice that our midterm exam will be held in Room 105 (NOT in
the classroom we used to be) at
Coursework:
Midterm exam (45%)
Oral presentation of selected topics or papers (40%)
Homework and class participation (15%)
Our classmates …
Classmates (I) (left)
Classmates (II) (middle)
Classmates (III) (right)
Classmates (IV) (standing)
Classmates (V) (newcomers)
Classmates (VI) (more)
Classmates (VII) (more and more)
Classmates (VIII) (more3)
Classmates (IX) (more4)
Magic shows in our break: (
Class PowerPoint slides:
Routing Load (by 志宣)
Minimum Routing Cost Spanning Trees
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
A note on optimal communication spanning trees (bonus points here)
A note on eccentricities, diameters, and radii
Wu, B. Y., Chao, K. -M.
and Tang, C. Y. , 2000, “Approximation
Algorithms for the Shortest Total Path Length Spanning Tree Problem,” Discrete Applied Mathematics, 105:
273-289.
Wu, B. Y., Lancia, G., Bafna,
V., Chao, K. -M., Ravi, R. and Tang, C. Y. , 2000, A
Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees, SIAM Journal on Computing, 29: 761-778.
Notes by 婉嫣
Class presentations:
1. Maximum number of team members: 6
2. Each member is required to present in turn;
3. Revised slides should be sent to me one week after the presentation;
4. Every student is required to submit a brief note right after the presentation;
5. Questions in class are always welcome;
Selected papers for presentation:
(These papers are very tough. Be prepared.)
4/22
V. King. A simpler minimum
spanning tree verification algorithm. Algorithmica, 18:263–270,
1997.
陳建宏 傅琳智 林書平 莊弼皓 張延聖
Slides
4/29
B. Chazelle. A
minimum spanning tree algorithm with inverse-Ackermann type complexity. J.
ACM, 47:1028–1047, 2000.
江盈宏 吳光哲 陳彥宏
S. Pettie and
V. Ramachandran. An
optimal minimum spanning tree algorithm. J. ACM, 49:16–34, 2002.
余家興 鍾至衡 張碧娟
5/6
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.
馬德文 黃拓儒
5/13
M. Thorup. Undirected
single-source shortest paths with positive integer weights in linear time. J.
ACM, 46:362–394, 1999.
巨彥霖 羅婉嫣 許恆瑞
M. Thorup. On RAM priority queues.
鄭智懷 田知本 袁維均
5/20 No class
5/27
S. Khuller,
B. Raghavachari, and N. Young. Low
degree spanning trees of small weight.
葉恆青 高孟駿 趙坤茂
6/3
D-.Z Du and
F.K. Hwang. A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica,
7:121–135, 1992.
洪俊竹 洪浩舜 蔡秉穎 梅普華
Slides
6/10
H.S.
Connamacher and A. Proskurowski. The complexity of
minimizing certain cost metrics for k-source spanning trees. Discrete
Appl. Math., 131:113–127, 2003.
劉效飛 田文錦 蕭志亘 林容任 王弘倫 胡淑瓊
References (not required):
1.
Spanning
Trees and Optimization Problems, by Bang Ye Wu and Kun-Mao Chao (2004),
Chapman & Hall/CRC
2. Related journal and conference papers
