Course: Special topics on graph algorithms
Spring semester, 2009
Monday 13:20 - 16:20, 105 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree09spr
Instructor: Kun-Mao Chao (趙坤茂)
TA: Cheng-Wei Luo (羅正偉)
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 2009/3/30 & 2009/5/11)
Oral presentation of selected topics or papers (20%)
Homework and class participation (10%)
Our classmates: I II III IV V VI VII VIII IX X XI XII (2009/02/16) || XIII (2009/06/08)
Class notes:
Counting Spanning Trees [2009/02/16]
Minimum Spanning Trees [2009/02/23]
Shortest-Paths Trees [2009/03/02]
A note on a 2-approximation algorithm for the MRCT problem [2009/03/09]
A note on 15/8 & 3/2-approximation algorithms for the MRCT problem [2009/03/09 - 3/23; Exam#1: 2009/3/30]
A note on a polynomial time approximation scheme for the MRCT problem (More details)
Optimal Communication Spanning Trees [2009/4/6]
A 2-approximation algorithm for the SROCT problem [2009/4/6 & 2009/4/13]
A note on eccentricities, diameters, and radii [2009/4/13]
Steiner Minimal Trees
[2009/4/20]
A note on the uniform edge-partition of a
tree [2009/4/27] [Exam#2: 2009/5/11]
The Tree Interval Cover Problem [2009/5/4]
Slides:
Introduction [2009/02/16]
Counting Spanning Trees [2009/02/16]
Riddles [2009/02/16]
Minimum Spanning Trees [2009/02/23]
Shortest-Paths Trees [2009/03/02]
Minimum Routing Cost Spanning Trees [2009/03/09 - ]
Homework:
Class presentations:
1. Suggested number of team members: about 6
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.)
2009/5/18
Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell:
The Minimum-Area Spanning
Tree Problem. WADS 2005: 195-204.
何宗融 沈孟俞 蔡鎮宇 蔡予欣 江宗憲 黃安達
Beat Gfeller:
Faster Swap Edge Computation in Minimum Diameter Spanning Trees. ESA 2008:454-465.
陳鵬仁 張凱崴 余相甫 徐國鐘 鄒承孝 沈 定 陳學毅
2009/5/25
Refael Hassin, Asaf Levin:
Approximation Algorithms for Quickest Spanning Tree
Problems. Algorithmica 41(1): 43-52, 2004.
何元臣 施佩汝 洪家榮 陳裕美 劉冠廷
Maleq Khan, Gopal Pandurangan, V. S. Anil Kumar:
Distributed Algorithms for
Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks.
IEEE Trans. Parallel Distrib. Syst. 20(1):124-139, 2009.
楊孟翰 簡廷因 陳怡安 林明志 盧曉珍 孫安承
Slides
Photo
2009/6/1
Sanjiv Kapoor, H. Ramesh:
Algorithms for Enumerating All Spanning Trees of
Undirected and Weighted Graphs. SIAM J. Comput. 24(2): 247-265, 1995.
張仕明 李孟哲 陳翰霖
Slides
Sanjiv Kapoor, H. Ramesh:
An Algorithm for Enumerating All Spanning Trees of a
Directed Graph. Algorithmica 27(2): 120-130, 2000.
林蔚茵 莊秋芸 李孟韓 黃稚穎
Slides
Photo
Navin Goyal, Luis Rademacher, Santosh Vempala: Expanders via random spanning trees. SODA 2009: 576-585.
黃怡嘉 黃佳婷 許榮財
2009/6/8
M. Thorup.
Undirected single-source shortest paths with positive
integer weights in linear time. J. ACM, 46:362–394, 1999.
陳縕儂 呂哲安 胡升鴻 陳代樾 黃鈞愷 張愈敏
Optional:
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.)
Baruch Awerbuch, Israel Cidon, Shay Kutten: Optimal maintenance of a spanning
tree. J. ACM, 55(4), 2008.
Lamberti, F. Sanna, A. Demartini, C.: A Relation-Based Page Rank Algorithm for Semantic Web Search Engines. IEEE Transactions on Knowledge and Data Engineering, 21: 123-136, 2009
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
Handbook on Approximation Algorithms and Metaheuristics (edited by Prof. Teo Gonzalez)
