Course: Special topics on graph algorithms
Spring semester, 2010
9:10 - 12:10 Tuesday, 105 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree10spr
Instructor: Kun-Mao Chao (趙坤茂)
TA: Kuan-Yu Chen (陳冠宇)
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 April 13, 2010 and May 18, 2010)
Oral presentation of selected topics or papers (20%)
Homework and class participation (10%)
Our classmates: I II III IV V VII VIII (Feb. 23, 2010)
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
Steiner Minimal Trees
A note on the uniform edge-partition of a
tree
Slides:
Minimum Routing Cost Spanning Trees
Homework:
Class presentations:
1. Suggested number of team members: about 4-7
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:
(You may choose your own topic to present. Please talk to me in advance
if you wish to do so.)
5/25/2010
Xiaochun Wang, Xiali Wang, D. Mitch Wilkes: A Divide-and-Conquer Approach for Minimum Spanning Tree-Based Clustering. IEEE Trans. Knowl. Data Eng. (TKDE) 21(7):945-958 (2009)
蔡永信 施俊宇 魏斯俞 楊雅倫 吳其恩 林維迪 楊淳淵
Beat Gfeller: Faster Swap Edge Computation in Minimum Diameter Spanning Trees. ESA 2008:454-465.
蔡長蓉 周冠汝 洪晧瑜 黃詠筑
6/1/2010
Jonathan A. Kelner, Aleksander Madry: Faster Generation of Random Spanning Trees. FOCS 2009:13-21.
施鴻逸 黃柏翔 翁正勳 林峰生
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.
徐銘遠 黃博平 顏維彤 陳彥璋 洪凱峰 石 穎 周于荃
6/8/2010
V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18:263–270, 1997.
Torben Hagerup: An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees. WG 2009:178-189.
曾怡茹 趙偉伶 姚甯之 林君轂
M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46:362–394, 1999.
詹竣安 傅怡聖 蔣兆凱 嚴家成 沈之涯
6/15/2010
Bracken M. King, Bruce Tidor: MIST: Maximum Information Spanning Trees for dimension reduction of biological data sets. Bioinformatics 25(9):1165-1172 (2009)
曾聖耀 李政德 洪慧儒 高峻偉 高文洪 鄭亦珊
Other options:
Artur Czumaj, Christian Sohler:
Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM
J. Comput. (SIAMCOMP) 39(3):904-922 (2009)
Martin Knauer, Joachim Spoerhase: Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. WADS 2009:459-470
Henning Fernau, Serge Gaspers, Daniel Raible: Exact and Parameterized Algorithms for Max Internal Spanning Tree. WG 2009:100-111
Navin Goyal, Luis Rademacher, Santosh Vempala: Expanders via random spanning trees. SODA 2009: 576-585.
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.)
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
Special
topics on graph algorithms, Spring 2008
Special topics on graph algorithms, Spring 2009
Handbook on Approximation Algorithms and Metaheuristics (edited by Prof. Teo Gonzalez)
