Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
Startseite    Anmelden     
Sommer 2024    Hilfe  Trennstrich  Sitemap  Trennstrich  Impressum  Trennstrich  Datenschutz  Trennstrich  node2  Trennstrich  Switch to english language

Veranstaltung

Algorithmische Graphentheorie

  • Funktionen:

Grunddaten

Veranstaltungsart Integrierte Lehrveranstaltung SWS 4.00
Veranstaltungsnummer 23904 Semester SS 2023
Sprache Deutsch Studienjahr
Hyperlink Stud.IP Lehrveranstaltung nicht mit Stud.IP synchronisiert

Belegung über StudIP

Es gibt keine Informationen zu einem Belegungsverfahren.

Termine Gruppe: [unbenannt] iCalendar Export für Outlook

  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer/-innen
Einzeltermine anzeigen
iCalendar Export für Outlook
Di. 15:00 bis 17:00 woch 04.04.2023 bis 11.07.2023  A.-Einstein-Str. 22 - SR 109, A.-Einstein-Str. 22 Raumplan Schmidt findet statt    
Einzeltermine anzeigen
iCalendar Export für Outlook
Do. 09:00 bis 11:00 woch 06.04.2023 bis 13.07.2023  A.-Einstein-Str. 22 - SR 110, A.-Einstein-Str. 22 Raumplan Schmidt findet statt    
Gruppe [unbenannt]:
 

Verantwortliche Person

Verantwortliche Person Zuständigkeit
Prof. Dr. rer. nat. Jens Schmidt

Studiengänge

Studiengang/Abschluss/Prüfungsversion Semester Teilnahmeart
Computer Science International, Master (2020) 1. - 3. Semester wahlobligatorisch
Informatik, Master (2020) 1. - 2. Semester wahlobligatorisch

Zuordnung zu Einrichtungen

Fakultät für Informatik und Elektrotechnik (IEF)

Inhalt

Kommentar

Diese Vorlesung behandelt ausgewählte Bereiche der Algorithmischen Graphentheorie mit einem Fokus auf Zusammenhangsprobleme.

Voraussetzungen: Einführung in die Theoretische Informatik, Effiziente Graphenalgorithmen

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

Strukturbaum

Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SS 2023 , Aktuelles Semester: Sommer 2024