Ausfallsicheres Broadcasting durch Unabhängige Spannbäume

• Antragsteller: Professor Dr. Jens M. Schmidt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 401348462

• Erstellungsjahr: 2025

Zusammenfassung der Projektergebnisse

Viele Probleme der theoretischen Informatik sind durch Graphen modellierbar, d.h. durch abstrakte Wegenetze, in denen beispielsweise Städte durch Knoten und Wegeverbindungen zwischen diesen Städten durch Kanten repräsentiert werden. Die zentrale Fragestellung ist dabei, wie schnell diese Probleme automatisiert, d.h. mit Hilfe von Algorithmen, gelöst werden können. Klassischerweise werden die größten Fortschritte in der Entwicklung und Analyse dieser Graphenalgorithmen durch neue strukturelle Erkenntnisse in der Graphentheorie gewonnen. Dieses Projekt setzt den Schwerpunkt auf die graphentheoretischen Grundlagen der Ausfallsicherheit von Broadcasts. Bei einem Broadcast sendet ein spezieller Knoten r (wir nennen diesen Wurzel) eines Graphen ein Datenpaket zu allen anderen Knoten. Soll in einem Graphen G von Wurzel r aus ein Broadcast gesendet werden, muss jeder andere Knoten von r aus erreichbar sein. Damit ist ein Broadcast genau dann möglich, wenn G einen an r gewurzelten Spannbaum enthält; entlang diesem kann das Datenpaket dann auch geroutet werden. Allerdings ist ein einziger Spannbaum nicht tolerant gegenüber dem Ausfall einer einzigen Kante oder eines einzigen Knotens. Die Ausfallsicherheit eines Netzwerks bezüglich Broadcasts wird deswegen wie folgt definiert: Seien zwei an r gewurzelte Bäume T und T 0 unabhängig, wenn für jeden Knoten v ∈ T ∩ T 0 die eindeutigen Pfade von r nach v in T und T0 jeweils intern knotendisjunkt sind. Die Ausfallsicherheit eines Graphen mit Wurzel r ist die maximale Anzahl von enthaltenen an r gewurzelten Spannbäumen, die paarweise unabhängig sind. Für polyedrische Graphen sind mehrere Strukturen bekannt, die einem die maximale Anzahl 3 der obigen unabhängigen Spannbäume geben. Eine der Bekanntesten sind sogenannte Schnyderwälder.

Projektbezogene Publikationen (Auswahl)

• 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.