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.

Preliminary course outlines

****** Notice that our midterm exam will be held in Room 105 (NOT in the classroom we used to be) at 14:20, April 15, 2004. ******

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) (more³)

Classmates (IX) (more⁴)

Magic shows in our break: (March 11, 2004)

Class PowerPoint slides:

First class

Counting Spanning Trees

Minimum Spanning Trees

Shortest-Paths Trees

Routing Load (by 志宣)

Minimum Routing Cost Spanning Trees

upper_bound.jpg

2&3stars.jpg

Class notes:

Counting Spanning Trees

Minimum Spanning Trees

Shortest-Paths Trees

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.

余家興鍾至衡張碧娟

Slides_1

Slides_2

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.

馬德文黃拓儒

Slides

5/13

M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46:362–394, 1999.
巨彥霖羅婉嫣許恆瑞

Slides

M. Thorup. On RAM priority queues. SIAM J. Comput., 30:86–109, 2000.

鄭智懷田知本袁維均

Slides_1

Slides_2

Slides_3

5/20 No class

5/27

S. Khuller, B. Raghavachari, and N. Young. Low degree spanning trees of small weight. SIAM J. Comput., 25:355–368, 1996.

葉恆青高孟駿趙坤茂

Slides

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.

劉效飛田文錦蕭志亘林容任王弘倫胡淑瓊

Slides

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