verantwortlich
Prof. Dr. Manfred Kunde und Dipl.-Inf. Sascha Grau

[Mitteilungen] [Inhalte] [Vorträge und Termine] [Literatur]

Mitteilungen

• Bei Interessese an der Bearbeitung eines Themas, melden sie sich bitte bei Herrn Grau.

• Für den Scheinerwerb wird ein etwa einstündiger Vortrag über das ausgewählte Thema und die Teilnahme an mindestens 80% der Veranstaltungen erwartet.
  

Inhalte

Der Kanten- und Knotenzusammenhang von Graphen spielt eine wichtige Rolle beim Design robuster und ausfalltoleranter Kommunikationsnetzwerke. Die Maße garantieren dabei den Fortbestand der Kommunikationsmöglichkeit auch bei Ausfall einer bestimmten Anzahl von Kanten bzw. Knoten.

Insbesondere durch die Loslösung von der Berechnung maximaler Flüsse, hat es bei der Bestimmung des Kantenzusammenhangs große Fortschritte gegeben.

Die Themen in diesem Hauptseminar werden sich hauptsächlich mit der Bestimmung und Erhöhung des Kanten- bzw. Knotenzusammenhangs beschäftigen.  Außerdem sollen Einblicke in die Erhöhung des lokalen Kantenzusammenhangs gegeben und Grenzen seiner Berechenbarkeit in polynomieller Zeit aufgezeigt werden.

Vorträge und Termine

Die folgenden Themen sind vorgesehen:

• Berechnung Minimaler Schnitte mittels Adjazenzordnungen

• Berechnung von Gomory-Hu-Bäumen und Anwendungsmöglichkeiten

• Extreme Mengen, Cactus-Repräsentation und Erhöhung des
  Kantenzusammenhangs um Eins

• Erhöhung des Kantenzusammenhangs mittels Kantenteilung

• Komplexität und Approximierbarkeit der Augmentierung des
  Kantenzusammenhangs zwischen Graphregionen

• Augmentierung des lokalen Kantenzusammenhangs zwischen Knoten und
  Knoten-Regionen

• Knotenzusammenhang eines Graphen: Klassische Algorithmen und 2-Approximation

Bei Bedarf ist die Ausgabe weiterer Themen möglich.

Literatur

Die Teilnehmer erhalten jeweils die ihrem Thema zugrunde liegenden Origininalveröffentlichungen in englischer Sprache.
Die Nutzung von Sekundärliteratur ist erlaubt und ausdrücklich erwünscht.

Thema 1:

- Stoer,Wagner: A simple mincut-algorithm 
- Brinkmeier: A simple and fast min-cut algorithm

Thema 2:

 Berechnungsverfahren:
 - Gomory, Hu: Multi-Terminal Network Flows
 - Goldberg, Tsioutsiouliklis: Cut-Tree Algorithms
 Anwendung:
 - Nagamochi: Graph algorithms for network connectivity problems

Thema 3:

 - Nagamochi: Graph algorithms for network connectivity problems

Thema 4:

 - Nagamochi: Graph connectivity and its augmentation: applications of MA orderings

Thema 5:

 - Ishii, Makino: Augmenting edge-connectivity between vertex subsets

Thema 6:

 - Ishii, Hagiwara: Minimum Augmentation of Local Edge-Connectivity
   between Vertices and Vertex Subsets in Undirected Graphs

Thema 7:

 - Even, Tarjan: Network Flow and Testing Graph Connectivity
 - Henzinger, Rao, Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques
   (zur Ergänzung und Einordnung des obigen Papers)
 - Henzinger: A static 2-approximation algorithm for vertex-connectivity and incremental approximation 
   algorithms for edge and vertex connectivity