Vorlesung Algorithmic Graph Theory (WS 96/97)

Artur Czumaj

Termine

Vorlesung (V2)

Dienstag 14:00 - 16:00 F1.110

Artur Czumaj: Email: artur@uni-paderborn.de; Raum: F1.316; Telefon: (05251) 60-6491

Inhaltsübersicht:

Wir stellen neuere Ergebnisse und Algorithmen für klassische Probleme der Graphentheorie vor. Die folgenden Probleme werden untersucht:

Sequentielle und Parallele Algorithmen für Zusammenhang und k-Zusammenhang
Zusammenhang unter Speicherrestriktionen
Minimale spannende Bäume (linearzeit Algorithmus)
Maximum Matching (grundlegende sequentielle Techniken und parallele Algorithmen)
Kürzeste Weg Problem
...

Alle genannten Probleme haben relativ einfache (im allgemeinen nicht optimale) Löosungen. In diesem Kurs konzentrieren wir uns auf Algorithmen, die entweder optimal sind, oder aber effizienter als Standardlöosungen.

Dieser Kurs wird in englischer Sprache gelesen.

Date	Topic
Oct 8	Introduction
Oct 15	Efficient parallel connectivity
Oct 22	s-t connectivity on log-space probabilistic Turing machines
Oct 29	Undirected connectivity in O(log^{1.5} n) space
Nov 5	On-line connectivity
Nov 12	Fully dynamic connectivity
Nov 19	Parallel maximum matching in cubic bipartite graphs
Nov 26	Parallel maximum matching in cubic bipartite graphs (cnt)
Dec 3	Parallel maximum matching in cubic bipartite graphs (cnt)
Dec 10	PTAS for 2-dimensional Euclidean TSP
Jan 7	PTAS for 2-dimensional Euclidean TSP (cnt)
Jan 14	PTAS for 2-dimensional Euclidean TSP (cnt) and Minimum spanning trees
Jan 21	Minimum spanning trees and verification of MST
Jan 28	Verification of minimum spanning trees (cnt)
Feb 4	Randomized linear-time minimum spanning tree
Feb 11	Exploring unkown environment

Literatur: Forschungpapers

J. JaJa, An Introduction to Parallel Algorithms, Addison-Wesley, 1991.
R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics (SIAM), 1983.
N. Nisan, E. Szemeredi, and A. Wigderson, Undirected connectivity in O(log^{1.5}) space, 33rd FOCS, pages 24-29, 1992.
Y. Dinitz, Mainatining the 4-edge-connected components of a graph on-line, 2nd ISTCS, pages 88-97, 1993.
M. Rauch Henzinger and V. King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, 27th STOC, pages 519-527, 1995.
R. Sharan and A. Wigderson, A new NC algorithm for perfect matching in bipartite cubic graphs, 4th ISTCS, 1996.
A. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, 37th FOCS, pages 2-11, 1996.
V. King, A simpler minimum spanning tree verification algorithm, WADS 1995.
D. R. Karger, P. N. Klein, and R. E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, JACM 42, 1995.
X. Deng and C. Papadimitriou, Exploring an unkown graph, 31st FOCS, pages 355-361, 1990.
S. Albers and M. R. Henzinger, Exploring unkown environments, STOC 1997.