Resilient Broadcasting via Independent Spanning-Trees
Final Report Abstract
Many problems in theoretical computer science can be modeled by graphs, that is, abstract path networks in which cities are represented by nodes and path connections between these cities are represented by edges. The central question is how quickly these problems can be solved automatically, that is, with the help of algorithms. Traditionally, the greatest advances in the development and analysis of these graph algorithms are gained through new structural insights in graph theory. This project focuses on the graph-theoretical foundations of reliable broadcasts. In a broadcast, a special node r (we call this root) of a graph sends a data packet to all other nodes. If a broadcast is to be sent from root r in a graph G, every other node must be reachable from r. This means that a broadcast is only possible if G contains a spanning tree rooted at r; the data can then be routed along this tree. However, a single spanning tree is not tolerant of the failure of a single edge or a single node. The general resilience of a network with respect to broadcasts is therefore defined as follows: Let two trees T and T0 rooted at r be independent if for each node v ∈ T ∩ T 0 the unique paths from r to v in T and T0 are internally node-disjoint. The resilience of a graph with root r is now the maximum number of contained spanning trees rooted at r that are pairwise independent. For polyhedral graphs, several structures are known that give the maximum number 3 of the above independent spanning trees. One of the most known ones are so-called Schnyder woods.
Publications
-
grApp. In 29th International Symposium on Graph Drawing and Network Visualization. LNCS series vol. 12868, 2021
I. N. Ivanov & J. M. Schmidt
-
Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs. Lecture Notes in Computer Science, 19-30. Springer Nature Switzerland.
Ortlieb, Christian
-
Toward Grünbaum’s conjecture bounding vertices of degree 4. In Proceedings of the 25th Italian Conference on Theoretical Computer Science (ICTCS’24), volume 3811 of CEUR Workshop Proceedings, pages 173–185, 2024
C. Ortlieb
-
Toward Grünbaum’s conjecture for 4-connected graphs. In: Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS’24), volume 306 of Leibniz International Proceedings in Informatics, pages 77:1–77:13, 2024
C. Ortlieb
-
Toward Grünbaum’s conjecture. In: Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’24), volume 294 of Leibniz International Proceedings in Informatics, pages 37:1–37:17, 2024
C. Ortlieb & J. M. Schmidt
-
Trees and co-trees in planar 3-connected graphs. An easier proof via Schnyder woods
C. Ortlieb & J. M. Schmidt
-
Minimal Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs. Lecture Notes in Computer Science, 225-237. Springer Nature Switzerland.
Ortlieb, Christian
-
Structural parameters of Schnyder woods. Discrete Mathematics, 348(2), 114282.
Ortlieb, Christian & Schmidt, Jens M.
