Course: Special topics on graph algorithms
Fall semester, 2010
9:10 - 12:10 Tuesday, 111 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree10fall
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 Oct. 26, 2010 and Dec. 7, 2010)
Oral presentation or implementation of selected topics or papers (20%)
Homework and class participation (10%)
Our classmates: I II III IV V VI VII VIII IX X
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
((4/3+epsilon)-approximation: Approximation Algorithms for the Shortest Total Path Length Spanning Tree 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
Examples: I
II III
A note on (4/3+epsilon)-approximation
A note on the reduction to the metric case
A note on the PTAS for the MRCT problem (A rough estimate for a delta-path)
Homework:
Class presentations:
1. Suggested number of team members: about 7~8
2. Each member is required to present in turn;
3. Revised slides should be sent to me within 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.)
D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan.
The
Complexity of the Network Design Problem. Networks, 279-285, 1978.
12/14 No Class
12/21 楊凱文 吳彥緯 陳琨 張允耀 傅莉雯
Slides
Kevin Buchin and André Schulz.
On the Number of Spanning Trees a Planar Graph Can Have. ESA 2010,
110-121, 2010.
12/21 葉士賢 林建旻 蕭聖穎 張琮勛 賴俊鳴
Slides
Pierluigi Crescenzi, Roberto Grossi, Claudio Imbrenda, Leonardo Lanzi and
Andrea Marino.
Finding the Diameter in Real-World Graphs: Experimentally Turning a Lower
Bound into an Upper Bound. ESA 2010,
302-313, 2010.
12/28 施信瑋 方邵云 周邦彥 曹蕙芳 莊舜翔 林國偉 葉書豪
Slides
D. -Z. Du and F. K. Hwang. A Proof of the Gilbert-Pollak Conjecture on the Steiner Ratio. Algorithmica, 121-135, 1992.
N. Innami, B. H. Kim, Y. Mashiko and K. Shiohama.
The Steiner
Ratio Conjecture of Gilbert-Pollak May Still Be Open. Algorithmica,
869-872, 2010.
1/4 姚甯之 林書漾 黃詩晏 鄭宇婷 黃彥翔 吳宜庭 高新綠
何柏璋 王柏易
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
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
Special topics on graph algorithms, Spring 2010
Handbook on Approximation Algorithms and Metaheuristics (edited by Prof. Teo Gonzalez)
