■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
Ausgewählte Themen der Theoretischen Informatik
Automaten über unendlichen Objekten
Berechenbarkeit und Komplexität
Ergänzungen zu Mathematik I
Graphentheorie
Logik und Diskrete Strukturen
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Graphentheorie

Dozenten: Volker Diekert, Manfred Kufleitner

Übungen: Lukas Fleischer

Zeit Raum Termine
Mo 15:45–17:15 0.447 wöchentlich ab 12.10.
Do 15:45–17:15 0.447 wöchentlich (Vorlesung/Übung im Wechsel) ab 15.10.

Die Prüfung im Sommersemester 2016 findet am Freitag, den 14.10.2016, von 11:00 Uhr bis 13:00 Uhr in Raum 0.108 statt.

Die Prüfung im Wintersemester 2016/2017 findet am Freitag, den 28.04.2017, von 14:00 Uhr bis 16:00 Uhr in Raum 1.156 statt.

Vorlesungsinhalte

Die folgenden Themen und Konzepte wurden in der Vorlesung und in den Übungen behandelt:

  • Eulerkreise, Eulerwege, Hamiltonkreise, Satz von Ore
  • Knotengrade, Handschlaglemma, Schubfachprinzip
  • Bäume und Wälder, Cayley-Formel, Prüfer-Codes
  • Planarität, Eulerformel, Satz von Fáry-Wagner, Satz von Thomassen, Satz von Kuratowski, Testen auf Planarität in Polynomialzeit
  • Planare Separatoren, Satz von Lipton-Tarjan, Dualgraph, Berechnung planarer Separatoren in Linearzeit, Anwendungen
  • Färbungen, 3-Färbbarkeit ist NP-vollständig, 3-Färbbarkeit für planare Graphen ist NP-vollständig, 5-Färbbarkeit planarer Graphen, Kantenfärbungen
  • Satz von Hall, Heiratsbedingung, Stabile Heirat nach Gale-Shapley
  • AB-Separatoren, Satz von Menger, k-Zusammenhang, k-Kantenzusammenhang, unabhängige und kantendisjunkte Wege, Testen auf k-Zusammenhang in Polynomialzeit
  • Flussprobleme, Max-Flow-Min-Cut-Theorem, Algorithmus von Dinic
  • Graphparameter, Cliquen, unabhängige Mengen
  • Träger, Matchings, bipartite Graphen, Satz von Kőnig
  • Perfekte Graphen, α-Perfektheit, χ-Perfektheit
  • Cographen, Charakterisierungen von Cographen, Serien-Parallel-Graphen
  • Chordale Graphen, simpliziale Ordnungen, Separatoren in chordalen Graphen, Perfektheit chordaler Graphen, Berechnung simplizialer Ordnungen in Polynomialzeit, Intervallgraphen
  • Transitiv orientierbare Graphen, Ketten, Antiketten, Satz von Dilworth, Permutationsgraphen
  • Split-Graphen, Charakterisierungen von Split-Graphen
  • Gradsequenzen, Satz von Erdős–Gallai, Gradsequenzen von Split-Graphen
  • Schwache Vermutung für perfekte Graphen (Satz von Lovász)
  • Ramseytheorie, unendliche und endliche Version des Satzes von Ramsey, Ramsey-Zahlen

Übungsblätter

  • Blatt 1
  • Blatt 2
  • Blatt 3
  • Probeklausur – Update (05.02.2016): Die Single-Choice-Aufgaben zu k-Zusammenhang wurden umformuliert; die Randfälle sind jetzt ausgeschlossen.

Literatur

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.