Course: Special topics on graph algorithms
Spring semester, 2005
Wednesday
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree05spr
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:
Midterm exam (45%)
Oral presentation of selected topics or papers (40%)
Homework and class participation (15%)
Our classmates … I II III IV V
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 note on eccentricities, diameters, and radii
Slides:
Minimum Routing Cost Spanning Trees
Homework:
Problem 1: Find a master computer scientist to write about. Focus on the inspiration you got from him or her.
Problem 2: Define a new spanning tree problem. Write down your approach for solving it.
Your solutions could be in English or Chinese, and should be no more than two pages for each problem. E-mail your solutions in PDF format to me by May 25, 2005.
Class presentations:
1. Maximum number of team members: no more than three;
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:
4/27
Raja Jothi, Balaji Raghavachari: Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design. ICALP 2004: 805-818
黃耀廷 陳明江 李定達
5/4
Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink: Computing a (1+epsilon)-Approximate Geometric Minimum-Diameter Spanning Tree. Algorithmica 38(4): 577-589 (2004)
蔡翔宇 李穹軒 陳彥賓
5/11 (兩組)
Jochen Könemann, Asaf Levin, Amitabh Sinha II: Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem. Algorithmica 41(2): 117-129 (2004)
林清池 吳瑞渝
Christian Schindelhauer, Klaus Volbert, Martin Ziegler: Spanners, Weak Spanners, and Power Spanners for Wireless Networks. ISAAC 2004: 805-821
修丕承
5/18
Refael Hassin, Asaf Levin: Approximation Algorithms for Quickest Spanning Tree Problems. ESA 2004: 395-402
Refael Hassin, Asaf Levin: Approximation Algorithms for Quickest Spanning Tree Problems. Algorithmica 41(1): 43-52 (2004)
羅正偉 張家榮
5/25
Refael Hassin, Asaf Levin: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J. Comput. 33(2): 261-268 (2004)
李政崇 王維邦 洪智鐸
6/1
Michael Elkin: A faster distributed protocol for constructing a minimum spanning tree. SODA 2004: 359-368
張瑞賢 李龢軒 莊中豪
6/8
David Gamarnik: The Tutte Polynomial and the Expected Value of Random Minimal Length Spanning Tree of a Complete Graph. SODA 2005
林忠緯 張憶婷
6/15
Lap Chi Lau: An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. FOCS 2004: 61-70
鄭開明 陳絢昌 林信宏
Some related papers:
Spanning Trees:
Michael Elkin: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. STOC 2004: 331-340
Vittorio Bilò, Vineet Goyal, R. Ravi, Mohit Singh: On the Crossing Spanning Tree Problem. APPROX-RANDOM 2004: 51-60
Andréa C. dos Santos, Abilio Lucena, Celso C. Ribeiro: Solving Diameter Constrained Minimum Spanning Tree Problems in Dense Graphs. WEA 2004: 458-467
Steiner Trees:
Qi Zhu, Hai Zhou, Tong Jing, Xianlong Hong, Yang Yang: Efficient octilinear Steiner tree construction based on spanning graphs. ASP-DAC 2004: 687-690 (Just for reference; not for presentation)
C. N. Sze, Jiang Hu, Charles J. Alpert: A place and route aware buffered Steiner tree construction. ASP-DAC 2004: 355-360 (Just for reference; not for presentation)
Spanners:
Arthur M. Farley,
Andrzej Proskurowski,
Daniel Zappala,
Kurt J. Windisch: Spanners and message distribution in networks.
Discrete Applied Mathematics 137(2): 159-171 (2004)
Feodor F. Dragan, Chenyu Yan, Irina Lomonosov: Collective Tree Spanners of Graphs. SWAT 2004: 64-76
Michael Elkin, David Peleg: (1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput. 33(3): 608-631 (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:
Handbook on Approximation Algorithms and Metaheuristics (edited by Prof. Teo Gonzalez)
