Course: Special
topics on graph algorithms
Spring semester, 2007
Tuesday 10:20 - 13:10, 107 CSIE Building.
3 credits
Web site:
http://www.csie.ntu.edu.tw/~kmchao/tree07spr
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; 4/10/2007 & 5/15/2007)
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
Class notes:
Counting Spanning Trees
Minimum Spanning Trees
Shortest-Paths Trees
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
Steiner Minimal Trees
A note on eccentricities, diameters, and
radii
A note on the uniform edge-partition of a
tree
Slides:
First Class
Counting Spanning Trees
Minimum Spanning Trees
Shortest-Paths Trees
Homework:
Class presentations:
1.
Suggested number of team members:
about 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:
- May 22, 2007
C Feremans, A Grigoriev, R Sitters.
The geometric generalized minimum spanning tree problem with grid clustering,
A Quarterly Journal of Operations Research, 2006
(吳郁君 游岳齊 林信仲 萬高維 楊劭文)
Slides
SC Chang, LC Chen, WS Yang.
Spanning Trees on the Sierpinski Gasket,
Journal of Statistical Physics, Vol. 126, No. 3, February 2007
(王煜樟 楊伍隆 洪智鐸)
-
May 29, 2007
Paulden, T.
Smith, D.K.
From the Dandelion Code to the Rainbow code: a class
of bijective spanning tree representations with linear complexity and
bounded locality,
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 108- 123,
2006
(王凱平 杞俊賢 莊謹譽)
Slides
Sang-Moon SOAK.
A New Evolutionary Approach for the Optimal Communication Spanning Tree
Problem,
IEICE Transactions on Fundamentals of Electronics, Communications and
Computer Sciences, 2006 E89-A(10):2882-2893
(李振宇 陳麗徽 黃怡靜 洪嘉涓)
Slides
Prabha Sharma
Algorithms for the optimum communication spanning tree problem
Annals of Operations Research, Vol. 143, 203-209, 2006
(陳韋仰 朱韋妮 王釧茹)
Slides
- June 5, 2007
Megha Ladha and Earl E. Swartzlander, Jr.
Optimization of spanning tree adders,
Proceedings of SPIE -- Volume 6313, 2006.
(曾俊雄 賴韋志 巫祈賢)
Slides
E Angel, E Bampis, L Blin, L Gourvès.
Fair Cost-Sharing Methods for the Minimum Spanning Tree Game,
Information Processing Letters, 2006
(邱冠凱 胡啟政 劉宗灝 文國煒)
Slides
-
June 12, 2007
J. Puerto, A.M. Rodriguez-Chia,
A. Tamir, D. Perez-Brito
The bi-criteria
doubly weighted center-median path problem on a tree.
(吳佳欣 陳思佑 鄭仲鈞 高新綸)
Slides
R. Benkoczi, B. Bhattacharya, A.
Tamir
Collection Depots Facility
Location Problems in Trees.
(張經略 陳冠伶 李佳霖 王湘叡)
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:
