| Literatur |
H. Nagamochi, T. Ibaraki: Algorithmic Aspects of Graph Connectivity, 1st Edition, Cambridge University Press, 2008. J. Bang-Jensen and G. Gutin: Digraphs: Theory, Algorithms and Applications, 2nd Edition, 2008. B. Korte und J. Vygen - Combinatorial Optimization, 5th Edition, Springer, 2012. L. W. Beineke, R. J. Wilson: Topics in Structural Graph Theory, 1st Edition, Cambridge University Press, 2013. Verlinkte Originalpublikationen |
| Lerninhalte |
- Einführung, unit-cost RAM, Graph-Datenstrukturen, Topologische Sortierung - Definition Kanten- und Knotenzusammenhang, 2-Zusammenhang mit chain decompositions: Ohrendekompositionen, 2-Kanten- und 2-Zusammenhangstests, starke Orientierungen in jeweils Zeit O(n), Definition st-Orientierungen und -numberings - st-Orientierungen und -numberings (Badent 2002, Easy st-Numberings 2019), Block-Cut-Trees und 2-kontrahierbare Kanten in jeweils Zeit O(m) - 3-Zusammenhang, Tutte Splits, 3-Zusammenhangskomponenten - SPQR-Bäume + Berechnungsidee, Anzahl kombinatorischer Einbettungen planarer Graphen - Zertifizierende Algorithmen für 3-Zusammenhang, BG-Operationen, Bijektion zu BG-Pfaden und Existenz, Berechnung in Zeit O(n2) - Berechnung in Linearzeit, Tuttes Wheel-Theorem, Flussbasierte Knoten- und Kantenzusammenhangstests, Even-Tarjan, Bestimmung der Zusammenhangszahlen - Maximal Adjacency Orderings, Forest Decompositions und Folgerungen, Intervall- und weitere Eigenschaften - Sparsification, Pendant Pairs, Kantenzusammenhang in Zeit O(nm), Linear Decay, Matulas (2+eps)-Approximation in Zeit O(n+m) - Fluss-äquivalente Graphen, Gomory-Hu-Bäume für Graphen und symmetrische submodulare Mengenfunktionen - Dynamische Graphen, Euler-Tour Bäume, Dynamischer Zusammenhang in polylogarithmischer Zeit - Planaritätstest von Boyer-Myrvold in Zeit O(n): Walkup, Walkdown, Korrektheit, Kuratowski-Minorenextraktion - Geradlinige Zeichnungen, Kanonische Ordnungen, Shift-Algorithmus, Mondshein-Sequenz und Anwendungen: Alternativer Planaritätstest, Unabhängige Spannbäume, 3-Partitionsproblem, Planare st-Orientierungen, Barnettes Theorem - Partielle k-Bäume, Baumzerlegungen, Äquivalenz, Separatoren und Abgeschlossenheit, Berechnung der Baumweite - Dynamische Programmierung über Baumzerlegungen, 3-Färbbarkeit in Zeit O(32kkn), Schöne Baumzerlegungen, Courcelles Theorem und Konsequenzen |
