Course: Special topics on graph algorithms
Spring semester, 2006
Tuesday 9:10 - 12:10, 107 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree06spr
Instructor: Kun-Mao Chao (趙坤茂)
TA: Hsiao-Fei Liu (劉效飛)
Prerequisites: Some basic
knowledge on algorithm development is required. Background in approximation
algorithms is welcome but not required for taking this course.
Coursework:
Late midterm exam (45%)
Oral presentation of selected topics or papers (35%)
Homework and class participation (20%)
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
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:
Minimum Routing Cost Spanning Trees
Homework: Problem Set. (Handout: May 9, 2006; Due: June 13, 2006)
Class presentations:
1. Maximum number of team members: 4;
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:
Christos Theoharatos,
George Economou,
Spiros Fotopoulos: Color edge detection using the minimal spanning tree.
Pattern Recognition 38(4): 603-606 (2005)
Niina Päivinen: Clustering with a minimum spanning tree of scale-free-like
structure.
Pattern Recognition Letters 26(7): 921-930 (2005)
2006/5/9 陳怡靜 許秉慧 黃帥雨朋 陳芃安
Michael Laszlo,
Sumitra Mukherjee:
Minimum Spanning Tree Partitioning Algorithm for Microaggregation.
IEEE Trans. Knowl. Data Eng. 17(7): 902-911 (2005)
2006/5/16 歐政穎 吳瑞傑 林宗茂
Zvi Lotker,
Boaz Patt-Shamir,
Elan Pavlov,
David Peleg:
Minimum-Weight Spanning Tree Construction in O(log log
n) Communication Rounds.
SIAM J. Comput. 35(1): 120-131 (2005)
2006/5/23 翁書鈞 吳俐瑩 王尹 蕭俊宏 (旁聽) 謝卓叡
Artur Czumaj,
Funda Ergün,
Lance Fortnow,
Avner Magen,
Ilan Newman,
Ronitt Rubinfeld,
Christian Sohler:
Approximating the Weight of the Euclidean Minimum Spanning
Tree in Sublinear Time.
SIAM J. Comput. 35(1): 91-109 (2005)
2006/5/30 戴邦炘 黃昱豪
Abraham D. Flaxman,
Alan M. Frieze,
Michael Krivelevich:
On the random 2-stage minimum spanning tree.
SODA 2005: 919-926
2006/5/30 陳彥名 林正平 蕭舒方 (旁聽)
Timothy M. Chan: Finding the shortest bottleneck edge in a parametric
minimum spanning tree.
SODA 2005: 917-918
2006/6/6 曾文鴻 佘健生 李奇錚 林淑棻
Hassene Aissi,
Cristina Bazgan,
Daniel Vanderpooten:
Approximation Complexity of min-max (Regret) Versions
of Shortest Path, Spanning Tree, and Knapsack.
ESA 2005: 862-873
2006/6/13 藍永倫 陳婕妤 潘奕誠 吳妙嬬
Paz Carmi,
Matthew J. Katz,
Joseph S. B. Mitchell:
The Minimum-Area Spanning Tree Problem.
WADS 2005: 195-204
2006/6/20 王振宇 陳健偉 盧永豐 楊川岳
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:
