Course: Special topics on graph algorithms
Fall semester, 2026
9:10 - 12:10 Tuesdays, 105 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree26fall
Instructor: Kun-Mao Chao (趙坤茂)
TA:
Shu-Ling Fang (方淑玲)
r12922025 followed by @ntu.edu.tw
[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.
Please follow the NTU guideline for course selection. (Sorry that it's hard to reply to every enquiry email during the hectic season.)
Coursework:
Two midterm exams (35% each; tentatively on Oct. 13, 2026 and Nov. 24, 2026)
Oral presentation or implementation of selected topics or papers (20%; tentatively on Dec. 1, 8, and 15, 2026)
Homework and class participation (10%)
Lecture notes:
Introduction [9/8/2026]
Riddles [9/8/2026]
Counting spanning trees [9/8/2026]
Slides [9/8/2026]
The number of unlabeled spanning trees of $K_n$ [9/8/2026]
A bijection between labeled trees and Prüfer sequences by Prof. David Galvin [9/8/2026]
Minimum spanning trees [9/15/2026]
Slides [9/15/2026]
2-approx. for TSP with triangle inequality [9/15/2026]
Shortest-paths trees [9/15/2026]
Slides [9/15/2026]
A note on a 2-approximation algorithm for the MRCT problem []
MRCT_slides []
2-approximation_algorithm_slides []
A note on 15/8 & 3/2-approximation algorithms for the MRCT problem []
Slides []
Bounds for the routing load of a minimal separator []
(4/3+epsilon)-approximation: Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem
Slides []
A note on a polynomial time approximation scheme for the MRCT problem (More details) []
The reduction to the metric case []
The PTAS for the MRCT problem (A rough estimate for a delta-path) []
Optimal communication spanning trees []
A 2-approximation algorithm for the SROCT problem []
Slides []
(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 []
Slides
[]
An example showing that the
farthest vertex of any vertex may not lie in the diameter
[]
Graph Theory: 51. Eccentricity, Radius & Diameter by Sarada Herke []
Slides []
(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 []
Slides []
(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))
A note on the minimum spanning tree cycle intersection problem
(Note:
M. Dubinsky, C. Massri, and G. Taubin. Minimum spanning tree cycle intersection problem. Discrete Applied Mathematics, 294:152, 2021.
M.-J. Chen and K.-M. Chao. Proof of a conjecture about minimum spanning tree cycle intersection. Discrete Applied Mathematics, 321:19, 2022.)
Class presentations:
1. Suggested number of team members: 1~5
2. Each member is required to present in turn [about x minutes each; roughly 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.
Dec. 1, 2026
-----------
Dec. 8, 2026
-----------
Dec. 15, 2026
Selected papers for presentation:
(Another option is that you may choose your own topic to present. Please talk to me in advance
if you wish to do so.)
Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub
Tetek:
Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. FOCS 2024: 2099-2130
Ran Duan,
Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin:
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. STOC
2025: 36-44
Ran Duan,
Xiao Mao, Xinkai Shu, Longhui Yin:
A Faster Directed Single-Source Shortest Path Algorithm. ICALP 2026:
81:1-81:23
Aaron
Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen:
Negative-Weight Single-Source Shortest Paths in Near-linear Time. J. ACM
72(4): 23:1-23:34 (2025)
(conference version: FOCS 2022: 600-611)
To be continued...
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
