Course

Course: Special topics on graph algorithms

Fall semester, 2011

9:10 - 12:10 Monday, 105 CSIE Building.

3 credits

Web site: http://www.csie.ntu.edu.tw/~kmchao/tree11fall

Instructor: Kun-Mao Chao (趙坤茂)

TA: An-Chiang Chu (朱安強) I II

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. 24, 2011 and Dec. 5, 2011)

Oral presentation or implementation of selected topics or papers (20%)

Homework and class participation (10%)

Our classmates: I II III

Class notes:

Counting Spanning Trees [2011/9/19]

Minimum Spanning Trees [2011/9/26]

Shortest-Paths Trees [2011/9/26]

A note on a 2-approximation algorithm for the MRCT problem [2011/9/26; 2011/10/3]

A note on 15/8 & 3/2-approximation algorithms for the MRCT problem [2011/10/3; 2011/10/17]

((4/3+epsilon)-approximation: Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem) [2011/10/31]

A note on a polynomial time approximation scheme for the MRCT problem (More details)

Optimal Communication Spanning Trees [2011/11/7]

A 2-approximation algorithm for the SROCT problem [2011/11/7]

A note on eccentricities, diameters, and radii [2011/11/14]

Steiner Minimal Trees
A note on the uniform edge-partition of a tree [2011/11/21]

Slides:

Introduction [2011/9/19]

Counting Spanning Trees [2011/9/19]

Riddles [2011/9/19]

Minimum Spanning Trees [2011/9/26]

Shortest-Paths Trees [2011/9/26]

Minimum Routing Cost Spanning Trees [2011/9/26 - ]
Examples: I II III [2011/10/10 holiday readings]

A note on (4/3+epsilon)-approximation [2011/10/31]

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)
       An example showing that the farthest vertex of any vertex may not lie in the diameter [2011/11/21]
       k-split (by An-Chiang) [2011/11/28]

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 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.)

Dec. 12, 2011
D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan. The Complexity of the Network Design Problem. Networks, 279-285, 1978. (Former students' slides)
陳子筠李庚謙張庭耀黃博平陳彥璋王舜玄林君達
Slides
　
Dec. 19, 2011
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann: The Stackelberg Minimum Spanning Tree Game. Algorithmica 59(2):129-144 (2011) (Authors' slides)
彭姵晨扶雅恩李勻張凱富葉恩豪
Slides
　

Salipante SJ, Hall BG. Inadequacies of minimum spanning trees in molecular epidemiology. J Clin Microbiol. 2011 Oct;49(10):3568-75.

何秉聖
Slides

　
Dec. 26, 2011
Gonzalo Navarro, Rodrigo Paredes: On Sorting, Heaps, and Minimum Spanning Trees. Algorithmica 57(4):585-620 (2010)
徐聖哲鄭龍蟠林霓苗陳雍協簡妙恩楊立德甘泰瑋
Slides

Jaewon Oh, Iksoo Pyo and Massoud Pedram: "Constructing minimal spanning/Steiner trees with bounded path length." European Design and Test Conference, 1996.
吳政穎
Slides
　
Jan. 2, 2012
Greg N. Frederickson: Optimal Algorithms for Tree Partitioning. SODA 1991:168-177. (A more detailed version)
謝宗潛許芷榕林澤豪駱家淮
Slides

Li-Sheng Chen, Hwang-Cheng Wang, Isaac Woungang and Fang-Chang Kuo: EOBDBR: an Efficient Optimum Branching-Based Distributed Broadcast Routing protocol for wireless ad hoc networks. Springer Telecommunication Systems, 2011
陳立勝
Slides