Course: Special topics on graph algorithms
Spring semester, 2019
9:10 - 12:10 Tuesday, 105 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree19spr
Instructor: Kun-Mao Chao (趙坤茂)
TA:
[TA's office hours: by appointment; Venue: R432]
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 Mar. 26, 2019 and May 14, 2019)
Oral presentation or implementation of selected topics or papers (20%)
Homework and class participation (10%)
Class notes:
Counting Spanning Trees [2019/2/19]
Minimum Spanning Trees [2019/2/26]
Shortest-Paths Trees [2019/2/26]
A note on a 2-approximation algorithm for the MRCT problem [2019/3/5]
A note on 15/8 & 3/2-approximation algorithms for the MRCT problem [2019/3/5, 2019/3/12, 2019/3/19]
((4/3+epsilon)-approximation: Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem) [2019/3/19]
A note on a polynomial time approximation scheme for the MRCT problem (More details) [2019/4/9, 2019/4/16]
Optimal Communication Spanning Trees [2019/4/23]
A 2-approximation algorithm for the SROCT problem [2019/4/23]
(Note:
S. V. Ravelo, C. E. Ferreira: A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem. Discrete Applied Mathematics 228: 158-175 (2017))
A note on the eccentricities, diameters, and radii [2019/4/30]
Steiner Minimal Trees [2019/5/7]
(Note:
N. Innami, B. H. Kim, Y. Mashiko, K.
Shiohama: The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open.
Algorithmica 57(4): 869-872 (2010)
Alexandr O. Ivanov, Alexey A. Tuzhilin: The
Steiner Ratio Gilbert-Pollak Conjecture Is Still Open - Clarification Statement.
Algorithmica 62(1-2): 630-632 (2012))
A note on the uniform edge-partition of a
tree [2019/5/7]
(Note:
Bang Ye Wu, Hung-Lung Wang, Shih Ta Kuan, and Kun-Mao Chao: On the uniform edge-partition of a tree. Discrete Applied Mathematics 155(10): 1213-1223 (2007)
An-Chiang Chu, Bang Ye Wu, and Kun-Mao Chao: A linear-time algorithm for finding an edge-partition with max-min ratio at most two. Discrete Applied Mathematics 161(7): 932-943 (2013)
Slides:
Introduction [2019/2/19]
Counting Spanning Trees [2019/2/19]
Riddles Happy Lantern Festival [2019/2/19]
The number of unlabeled spanning trees of $K_n$ [2019/2/26]
Minimum Spanning Trees [2019/2/26]
2-approx. for TSP with Triangle inequality [2019/2/26]
Shortest-Paths Trees [2019/2/26]
Minimum Routing Cost Spanning Trees [2019/3/5, 2019/3/12]
Blackboard: I
II III [2019/3/5]
Examples: I
II III
[2019/3/5]
A note on separators, general stars, and 3/2-approximation [2019/3/12]
A note on (4/3+epsilon)-approximation [2019/3/19]
A note on the reduction to the metric case [2019/4/9]
A note on the PTAS for the MRCT problem (A rough estimate for a delta-path) [2019/4/9, 2019/4/16]
A note on finding an optimal k-star [2019/4/16]
A note on OCT & SROCT [2019/4/23]
A
note on the eccentricities, diameters, and radii [2019/4/30]
An example showing that the
farthest vertex of any vertex may not lie in the diameter [2019/4/30]
Graph Theory: 51. Eccentricity, Radius & Diameter by Sarada Herke [2019/4/30]
A note on the Steiner minimal trees [2019/5/7; Thank Chan-Hung Hsu for his valuable comments. 2019/5/13]
A note on the uniform edge-partition of a tree [2019/5/7]
Class presentations:
1. Suggested number of team members: 1-6
2. Each member is required to present in turn [about 150/(the number of speakers on the same day) minutes each];
3. Revised slides should be sent to me within one week after the presentation;
4. Questions in class are always welcome.
(For those who haven't signed up for it, let me know your choice ASAP.)
May 21, 2019
Carlos Armando Zetina, Iván A. Contreras, Elena Fernández, Carlos Luna-Mota:
Solving the optimum communication spanning tree problem. European
Journal of Operational Research 273(1): 108-117 (2019)
劉達融 林東農 游育豪
R. Krithika, Rogers Mathew, N.S. Narayanaswamy, N. Sadagopan
A Dirac-type characterization of k-chordal graphs Discrete Mathematics 313(24): 2865-2867 (2013)
黃柏文
The broadcasting 2-center problem in weighted trees under postal model
徐展鴻
May 28, 2019
M
Kano, H Matsumura
Spanning trees with small diameters. AKCE International Journal of
Graphs and Combinatorics
Available online 29 March 2019
洪正皇 黃知盈 吳彥澄 沈泓宇 廖名淳 李祖源 黃博彥
June 4, 2019
Imtiaz Ahmed, Aldo Dagnino, Yu Ding:
Unsupervised Anomaly
Detection Based on Minimum Spanning Tree Approximated Distance Measures and
its Application to Hydropower Turbines. IEEE Trans. Automation Science
and Engineering 16(2): 654-667 (2019)
陳主牧 吳邦誠 林喬文 林育志 蕭大哲 陳耘志
Stefano Moriconi, Maria A. Zuluaga, H. Rolf Jäger, Parashkev Nachev,
Sébastien Ourselin, M. Jorge Cardoso:
Inference of Cerebrovascular Topology With Geodesic Minimum Spanning Trees.
IEEE Trans. Med. Imaging 38(1): 225-239 (2019)
王擎天
June 11, 2019
Günter Rote:
The
Maximum Number of Minimal Dominating Sets in a Tree. SODA 2019:
1201-1214
梁友銓 陳禹樵 楊書文
Rico Zenklusen:
A
1.5-Approximation for Path TSP. SODA 2019: 1539-1549
徐衍新
André Berger, László Kozma, Matthias Mnich, Roland Vincze:
A time-
and space-optimal algorithm for the many-visits TSP. SODA 2019:
1770-1782
李旭恩
Selected papers for presentation:
(You may choose your own topic to present. Please talk to me in advance
if you wish to do so.)
Martin Nägele, Rico Zenklusen:
A New
Dynamic Programming Approach for Spanning Trees with Chain Constraints and
Beyond. SODA 2019: 1550-1569
Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen:
Nearly ETH-tight algorithms for
Planar Steiner Tree with Terminals on Few Faces. SODA 2019: 1015-1034
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, Kevin Schewior:
A PTAS
for Euclidean TSP with Hyperplane Neighborhoods. SODA 2019: 1089-1105
Rico Zenklusen:
A
1.5-Approximation for Path TSP. SODA 2019: 1539-1549
André Berger, László Kozma, Matthias Mnich, Roland Vincze:
A time-
and space-optimal algorithm for the many-visits TSP. SODA 2019:
1770-1782
Günter Rote:
The
Maximum Number of Minimal Dominating Sets in a Tree. SODA 2019:
1201-1214
Greg Bodwin:
On the Structure of Unique
Shortest Paths in Graphs. SODA 2019: 2071-2089
Shiri Chechik, Sarel Cohen:
Near
Optimal Algorithms For The Single Source Replacement Paths Problem. SODA
2019: 2090-2109
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen:
Greedy
spanners are optimal in doubling metrics. SODA 2019: 2371-2379
Amir Nayyeri, Benjamin Raichel:
Viewing
the Rings of a Tree: Minimum Distortion Embeddings into Trees. SODA
2019: 2380-2399
Thiago Gouveia da Silva, Eduardo Queiroga, Luiz Satoru Ochi, Lucídio dos
Anjos Formiga Cabral, Serigne Gueye, Philippe Michelon:
A hybrid metaheuristic for the minimum labeling spanning tree problem.
European Journal of Operational Research 274(1): 22-34 (2019)
Carlos Armando Zetina, Iván A. Contreras, Elena Fernández, Carlos Luna-Mota:
Solving the optimum communication spanning tree problem. European
Journal of Operational Research 273(1): 108-117 (2019)
M
Kano, H Matsumura
Spanning trees with small diameters. AKCE International Journal of
Graphs and Combinatorics
Available online 29 March 2019
Imtiaz Ahmed, Aldo Dagnino, Yu Ding:
Unsupervised Anomaly
Detection Based on Minimum Spanning Tree Approximated Distance Measures and
its Application to Hydropower Turbines. IEEE Trans. Automation Science
and Engineering 16(2): 654-667 (2019)
Stefano Moriconi, Maria A. Zuluaga, H. Rolf Jäger, Parashkev Nachev,
Sébastien Ourselin, M. Jorge Cardoso:
Inference of Cerebrovascular Topology With Geodesic Minimum Spanning Trees.
IEEE Trans. Med. Imaging 38(1): 225-239 (2019)
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
