Course: Special topics on graph algorithms

Spring semester, 2021

9:10 - 12:10 Tuesday, 107 CSIE Building.

3 credits

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

Instructor: Kun-Mao Chao (趙坤茂)

TA:  張峯銘  pokedigi596 followed by @gmail.com
[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.

　

* All courses@NTU shall be switched to distance learning mode since May 17, 2021. The second midterm exam will be held remotely. I'll contact you via CEIBA@NTU later. [5/14/2021]

* A take-home exam will be given via CEIBA@NTU by May 18, 2021 and due on May 25, 2021. [5/15/2021]

* For the oral presentation in June, each team has to email me the file at least one day before the assigned date. The file format can be pdf, pptx, ecm, youtube, ... [5/15/2021]

* Midterm exam. #2 (Take-home exam.) has been posted via CEIBA@NTU. [14:00, 5/17/2021]

* The slides of class presentations have been uploaded... See Below. [6/1/2021, 6/8/2021, 6/15/2021]

　

Coursework:

Two midterm exams (35% each; tentatively on Mar. 30, 2021 and May 18, 2021, to be held remotely)

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

Homework and class participation (10%)

 

Our classmates: I  II  III  IV  V

　

Lecture notes:

       Introduction [2/23/2021]

       Riddles [2/23/2021]

       Counting spanning trees [2/23/2021, 3/2/2021]

               Slides [2/23/2021]      

               The number of unlabeled spanning trees of $K_n$ [2/23/2021]

               A bijection between labeled trees and Prüfer sequences by Prof. David Galvin [3/2/2021]

               Another note about the bijection by Prof. Victor Adamchik [3/2/2021]

       Minimum spanning trees [3/2/2021]

               Slides [3/2/2021]

               2-approx. for TSP with triangle inequality [3/2/2021]

       Shortest-paths trees [3/2/2021]

               Slides [3/2/2021]

       A note on a 2-approximation algorithm for the MRCT problem [3/2/2021, 3/9/2021]

               MRCT_slides [3/2/2021, 3/9/2021]

               2-approximation_algorithm_slides [3/9/2021]

               Examples: I  II  III  [3/9/2021]

       A note on 15/8 & 3/2-approximation algorithms for the MRCT problem [3/9/2021, 3/16/2021]

               Slides [3/9/2021, 3/16/2021; updated on 3/17/2021]

               Bounds for the routing load of a minimal separator [3/16/2021]

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

               Slides [3/23/2021; updated on 3/23/2021]

       A note on a polynomial time approximation scheme for the MRCT problem (More details) [4/13/2021, 4/20/2021]

               The reduction to the metric case [4/13/2021]

               The PTAS for the MRCT problem (A rough estimate for a delta-path) [4/13/2021, 4/20/2021]

               Finding an optimal k-star [4/13/2021, 4/20/2021]

       Optimal communication spanning trees [4/27/2021]

       A 2-approximation algorithm for the SROCT problem [4/27/2021]

               Slides [4/27/2021]

              (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/27/2021, 5/4/2021]

               Slides [4/27/2021, 5/4/2021; updated on 5/3/2021]
               An example showing that the farthest vertex of any vertex may not lie in the diameter [4/27/2021, 5/4/2021]

               Graph Theory: 51. Eccentricity, Radius & Diameter by Sarada Herke [5/4/2021]

       Steiner minimal trees  [5/4/2021, 5/11/2021]

               Slides [5/4/2021, 5/11/2021]

              (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 [5/11/2021]

               Slides [5/11/2021; updated on May 10, 2021]

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

　

Class presentations:

1.      Suggested number of team members: 1-6

2.      Each member is required to present in turn [about 15 minutes; 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 25, 2021 for preparation, no class]

　

June 1, 2021

Dongdong Cheng, Qingsheng Zhu, Jinlong Huang, Quanwang Wu, Lijun Yang:
Clustering with Local Density Peaks-Based Minimum Spanning Tree. IEEE Trans. Knowl. Data Eng. 33(2): 374-387 (2021)
闕中一 吳海韜

Slides [6/1/2021]

　

Shi Dong, Mudar Sarem, Wengang Zhou:
Distributed Data Gathering Algorithm Based on Spanning Tree. IEEE Syst. J. 15(1): 289-296 (2021)
沈培文 張峯銘

Slides [6/1/2021]

　

Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak:
Approximating Pathwidth for Graphs of Small Treewidth. SODA 2021: 1965-1976
林子欽 張 鈞

Slides [6/1/2021]

　

Grandoni et al: O(log2 k loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.

https://dl.acm.org/doi/abs/10.1145/3313276.3316349

塗大為 林庭風 黃于軒 彭道耘

Slides [6/1/2021]

　

June 8, 2021

Lin Yang, Yongjie Wang:
Prufer Coding: A Vectorization Method for Undirected Labeled Graph. IEEE Access 8: 175360-175369 (2020)
盧玉隆 楊雨樓
Slides [6/8/2021]

　

Linyuan Lu, Zhiyu Wang:
Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees. SIAM J. Discret. Math. 34(4): 2346-2362 (2020)
陳冠宇 陳威翰 鄭豫澤

Slides [6/8/2021]
　

Nina Kamcev, Anita Liebenau, David R. Wood, Liana Yepremyan:
The Size Ramsey Number of Graphs with Bounded Treewidth. SIAM J. Discret. Math. 35(1): 281-293 (2021)
邱允中 李哲安 賴開元

Slides [6/8/2021]

　

Julia Chuzhoy, Merav Parter, Zihan Tan:
On Packing Low-Diameter Spanning Trees. ICALP 2020: 33:1-33:18

許國讚

　

June 15, 2021

Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski:
Shorter Labels for Routing in Trees. SODA 2021: 2174-2193
呂明修 劉 昕 林宏信 周裕人

Slides [6/15/2021]

　

Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
Competitive Online Search Trees on Trees. SODA 2020: 1878-1891
黃光輝 劉厚辰 吳禹璇

Slides [6/15/2021]


Guido Besomi, Matías Pavez-Signé, Maya Stein:
Maximum and Minimum Degree Conditions for Embedding Trees. SIAM J. Discret. Math. 34(4): 2108-2123 (2020)
穆大有 王柏元

Slides [6/15/2021]
Oral_Report_1 [6/15/2021]
Oral_Report_2 [6/15/2021]

　

Selected papers for presentation:
(You may choose your own topic to present. Please talk to me in advance if you wish to do so.)

(You may access these selected articles using computers with NTU IP addresses.)

  1. Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski:
    Shorter Labels for Routing in Trees. SODA 2021: 2174-2193

  2. Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak:
    Approximating Pathwidth for Graphs of Small Treewidth. SODA 2021: 1965-1976

  3. Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman:
    Competitive Online Search Trees on Trees. SODA 2020: 1878-1891

  4. Alan M. Frieze, Tomasz Tkocz:
    A randomly weighted minimum spanning tree with a random cost constraint. SODA 2020: 670-689

  5. Linyuan Lu, Zhiyu Wang:
    Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees. SIAM J. Discret. Math. 34(4): 2346-2362 (2020)

  6. Nina Kamcev, Anita Liebenau, David R. Wood, Liana Yepremyan:
    The Size Ramsey Number of Graphs with Bounded Treewidth. SIAM J. Discret. Math. 35(1): 281-293 (2021)

  7. Shi Dong, Mudar Sarem, Wengang Zhou:
    Distributed Data Gathering Algorithm Based on Spanning Tree. IEEE Syst. J. 15(1): 289-296 (2021)

  8. Dongdong Cheng, Qingsheng Zhu, Jinlong Huang, Quanwang Wu, Lijun Yang:
    Clustering with Local Density Peaks-Based Minimum Spanning Tree. IEEE Trans. Knowl. Data Eng. 33(2): 374-387 (2021)

  9. Julia Chuzhoy, Merav Parter, Zihan Tan:
    On Packing Low-Diameter Spanning Trees. ICALP 2020: 33:1-33:18

  10. Lin Yang, Yongjie Wang:
    Prufer Coding: A Vectorization Method for Undirected Labeled Graph. IEEE Access 8: 175360-175369 (2020)

  11. Guido Besomi, Matías Pavez-Signé, Maya Stein:
    Maximum and Minimum Degree Conditions for Embedding Trees. SIAM J. Discret. Math. 34(4): 2108-2123 (2020)

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