, Andrzej
Pelc:Deterministic rendezvous in infinite trees. Theor. Comput. Sci. 984: 114313 (2024)
吳政宏
Course: Special topics on graph algorithms
Spring semester, 2024
9:10 - 12:10 Tuesday, 105 CSIE Building.
3 credits
Web site: http://www.csie.ntu.edu.tw/~kmchao/tree24spr
Instructor: Kun-Mao Chao (趙坤茂)
TA:
Pin-Chun Huang (黃品淳)
r11922135
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.)
https://www.aca.ntu.edu.tw/WebUPD/acaEN/UAADForms/112-2selcou-eng.pdf
* A set of sample problems for Midterm Exam. #1 was announced via NTU COOL on March 20, 2024.
* Selected papers for presentation have been posted on April 2, 2024.
* Midterm #1's score histogram (updated on April 15, 2024)
* Presentation schedule now available (4/16/2024)
* No class on April 23, 2024.
Coursework:
Two midterm exams (35% each; tentatively on Mar. 26, 2024 and May 7, 2024)
Oral presentation or implementation of selected topics or papers (20%)
Homework and class participation (10%)
Our classmates: I II III IV V VI
Lecture notes:
Introduction [2/20/2024]
Counting spanning trees [2/20/2024]
Slides [2/20/2024]
The number of unlabeled spanning trees of $K_n$ [2/20/2024]
A bijection between labeled trees and Prüfer sequences by Prof. David Galvin [2/20/2024]
Minimum spanning trees [2/20/2024]
Slides [2/20/2024]
2-approx. for TSP with triangle inequality [2/20/2024]
Shortest-paths trees [2/27/2024]
Slides [2/27/2024]
A note on a 2-approximation algorithm for the MRCT problem [2/27/2024]
MRCT_slides [2/27/2024, 3/19/2024]
2-approximation_algorithm_slides [2/27/2024, 3/5/2024]
Examples: I II III [2/27/2024]
A note on 15/8 & 3/2-approximation algorithms for the MRCT problem [3/5/2024]
Slides [3/5/2024, 3/12/2024]
Bounds for the routing load of a minimal separator [3/5/2024]
(4/3+epsilon)-approximation: Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem
Slides [3/12/2024, 3/19/2024]
A note on a polynomial time approximation scheme for the MRCT problem (More details) [3/19/2024, 4/2/2024]
The reduction to the metric case [3/19/2024, 4/2/2024]
The PTAS for the MRCT problem (A rough estimate for a delta-path) [4/2/2024]
Finding an optimal k-star [4/2/2024, 4/9/2024]
Optimal communication spanning trees [4/9/2024]
A 2-approximation algorithm for the SROCT problem [4/9/2024, 4/16/2024]
Slides [4/9/2024, 4/16/2024]
(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 [4/16/2024]
Slides
[4/16/2024]
An example showing that the
farthest vertex of any vertex may not lie in the diameter
[4/16/2024]
Graph Theory: 51. Eccentricity, Radius & Diameter by Sarada Herke [4/16/2024]
(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
(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 10~12 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.
May 14, 2024
Shang-En Huang, Dawei
Huang, Tsvi
Kopelowitz, Seth Pettie, Mikkel
Thorup:
Fully Dynamic Connectivity in O(log n(loglog n)2) Amortized
Expected Time. TheoretiCS 2 (2023)
劉宇倫 蘇子碩 陳建宏 譚雋飛 趙容
Jesper
Jansson, Wing-Kin
Sung, Seyed
Ali Tabatabaee, Yutong
Yang:
A Faster Algorithm for Constructing the Frequency Difference Consensus Tree. STACS 2024: 43:1-43:17
MARIA CAROLINA CORNELIA WIT and
PINTUSORN SUTTIPONPISARN
Subhash Bhagat, Andrzej
Pelc:
Deterministic rendezvous in infinite trees. Theor.
Comput. Sci. 984: 114313 (2024)
吳政宏
Miguel Licona, Joaquín
Tey:
Conservative trees. Discret.
Math. 347(3): 113854 (2024)
周昱宏 蔡莉亞 陳怜均
Samuel Thomas, Kidus
Workneh, Ange-Thierry
Ishimwe, Zack
McKevitt, Phaedra
S. Curlin, R.
Iris Bahar, Joseph
Izraelevitz, Tamara
Lehman:
Baobab Merkle Tree for Efficient Secure Memory. IEEE
Comput. Archit. Lett. 23(1): 33-36 (2024)
CASSANDRA LE PADELLEC and PAUL FEICHTENSCHLAGER
-----------
May 21, 2024
Rahul Jain, Raghunath
Tewari:
Space efficient algorithm for solving reachability using tree decomposition
and separators. Theor.
Comput. Sci. 982: 114251 (2024)
鐘奇恩 劉蕃熙 鄭百里 詹子慶 吳孟哲
Robert Hickingbotham, Freddie
Illingworth, Bojan
Mohar, David
R. Wood:
Treewidth, Circle Graphs, and Circular Drawings. SIAM
J. Discret. Math. 38(1): 965-987 (2024)
方淑玲
Samuel Eduardo da Silva, Uéverton
S. Souza:
Decoding Tree Decompositions from Permutations. LATIN
(1) 2024: 19-34
蔡斯昊 黃振嘉 盧冠綸 余書齊
-----------
May 28, 2024
Abel Cabrera Martínez:
Kennteth Dadedzi, Stephan
G. Wagner:
On the distribution of eigenvalues of increasing trees. Discret.
Math. 347(2): 113762 (2024)
呂宗澤 鞠睿陽 李昕叡 陳品睿
Silvia Tolo, John
D. Andrews:
Fault Tree Analysis Including Component Dependencies. IEEE
Trans. Reliab. 73(1): 413-421 (2024)
于珩 廖子言
Jack Dippel, Adrian
Vetta:
One n Remains to Settle the Tree Conjecture. STACS 2024: 28:1-28:16
簡謙益 蔡旻諺 王政祺 林秉軒
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.)
1.
Shang-En Huang, Dawei
Huang, Tsvi
Kopelowitz, Seth Pettie, Mikkel
Thorup:
Fully Dynamic Connectivity in O(log n(loglog n)2) Amortized
Expected Time. TheoretiCS 2 (2023)
劉宇倫 蘇子碩 陳建宏 譚雋飛 趙容
2.
Samuel Thomas, Kidus
Workneh, Ange-Thierry
Ishimwe, Zack
McKevitt, Phaedra
S. Curlin, R.
Iris Bahar, Joseph
Izraelevitz, Tamara
Lehman:
Baobab Merkle Tree for Efficient Secure Memory. IEEE
Comput. Archit. Lett. 23(1): 33-36 (2024)
CASSANDRA LE PADELLEC and PAUL FEICHTENSCHLAGER
3.
Amir Barghi, Daryl
R. DeFord:
Ranking trees based on global centrality measures. Discret.
Appl. Math. 343: 231-257 (2024)
4.
Egor Lappo, Noah
A. Rosenberg:
A lattice structure for ancestral configurations arising from the
relationship between gene trees and species trees. Discret.
Appl. Math. 343: 65-81 (2024)
5.
Abel Cabrera Martínez:
An improved upper bound on the domination number of a tree. Discret.
Appl. Math. 343: 44-48 (2024)
PAULO ENRIQUE LINARES OTOYA
6.
Kennteth Dadedzi, Stephan
G. Wagner:
On the distribution of eigenvalues of increasing trees. Discret.
Math. 347(2): 113762 (2024)
呂宗澤 鞠睿陽 李昕叡 陳品睿
7.
Miguel Licona, Joaquín
Tey:
Conservative trees. Discret.
Math. 347(3): 113854 (2024)
周昱宏 蔡莉亞 陳怜均
8.
Thomas Mattman:
A Novel Count of the Spanning Trees of a Cube. Graphs
Comb. 40(1): 19 (2024)
9.
Mikolaj Bojanczyk, Bartek
Klin:
Polyregular Functions on Unordered Trees of Bounded Height. Proc.
ACM Program. Lang. 8(POPL): 1326-1351 (2024)
10.
Ruben Becker, Yuval
Emek, Mohsen
Ghaffari, Christoph
Lenzen:
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions. SIAM
J. Comput. 53(2): 247-286 (2024)
11.
Robert Hickingbotham, Freddie
Illingworth, Bojan
Mohar, David
R. Wood:
Treewidth, Circle Graphs, and Circular Drawings. SIAM
J. Discret. Math. 38(1): 965-987 (2024)
方淑玲
12.
Pakawut Jiradilok, Supanat
Kamtue:
Transportation Distance between Probability Measures on the Infinite
Regular Tree. SIAM
J. Discret. Math. 38(1): 1113-1157 (2024)
13.
Subhash Bhagat, Andrzej
Pelc:
Deterministic rendezvous in infinite trees. Theor.
Comput. Sci. 984: 114313 (2024)
吳政宏
14.
Rahul Jain, Raghunath
Tewari:
Space efficient algorithm for solving reachability using tree decomposition
and separators. Theor.
Comput. Sci. 982: 114251 (2024)
鐘奇恩 劉蕃熙 鄭百里 詹子慶 吳孟哲
15.
Nicholas Galbraith, Samory
Kpotufe:
Classification Tree Pruning Under Covariate Shift. IEEE
Trans. Inf. Theory 70(1): 456-481 (2024)
16.
Silvia Tolo, John
D. Andrews:
Fault Tree Analysis Including Component Dependencies. IEEE
Trans. Reliab. 73(1): 413-421 (2024)
于珩 廖子言
17.
Kathryn Gray, Mingwei
Li, Abu
Reyan Ahmed, Md.
Khaledur Rahman, Ariful
Azad, Stephen
G. Kobourov, Katy
Börner:
A Scalable Method for Readable Tree Layouts. IEEE
Trans. Vis. Comput. Graph. 30(2): 1564-1578 (2024)
18.
Samuel Eduardo da Silva, Uéverton
S. Souza:
Decoding Tree Decompositions from Permutations. LATIN
(1) 2024: 19-34
蔡斯昊 黃振嘉 盧冠綸 余書齊
19.
Jesper Jansson, Wing-Kin
Sung, Seyed
Ali Tabatabaee, Yutong
Yang:
A Faster Algorithm for Constructing the Frequency Difference Consensus Tree. STACS 2024: 43:1-43:17
MARIA CAROLINA CORNELIA WIT and PLOY
20.
Jack Dippel, Adrian
Vetta:
One n Remains to Settle the Tree Conjecture. STACS 2024: 28:1-28:16
簡謙益 蔡旻諺 王政祺 林秉軒
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