Freitag, 10.11.2000, 16:00, Felix-Klein-Hörsaal HG 04-24

PD Dr. Jop F. Sibeyn

Department of Computing Science

Umeå University

"Effiziente externe Algorithmen für elementare Graphenprobleme"

Abstract:

Wir betrachten externe Algorithmen für einige grundlegende Graphenprobleme.

Externe Algorithmen sind Algorithmen für Probleme deren Eingabe nicht in den Hauptspeicher des Rechners hineinpasst, so dass bei ihnen ein Teil der Daten während der Berechnung ausgelagert werden muss. Die üblichen sequentiellen Algorithmen, mit ihren unstrukturierten Zugriffsmustern, verhalten sich bei solchen Problemen meist extrem schlecht.

Viele externe Probleme kann man O(optimal) lösen indem man einen PRAM Algorithmus nimmt und schrittweise simuliert. Da PRAM Algorithmen im Hinblick auf die Konstanten oft nicht besonders effizient sind und die Simulation nochmals einen zusätzlichen Verlustfaktor mit sich bringt, führt dieser Ansatz nur selten zu Algorithmen, die auch praktische Relevanz haben.

Für List-Ranking hat eine genaue Analyse zu einem neuen, einfachen und besonders effizienten Ansatz geführt, der sowohl extern als parallel einsetzbar ist. Es hat sich herausgestellt dass, dieser Ansatz im externen Kontext sogar über List-Ranking hinaus erweiterbar ist: auch für die Berechnung von kürzesten Wegen und vor allem für die Berechnung von Zusammenhangskomponenten führt er zu Berechnungszeiten die bisher kaum vorstellbar waren. Im Vortrag werde ich das allgemeine Prinzip dieses Ansatzes vorstellen, und zeigen wie man hiermit die drei genannten Probleme lösen kann. Dabei werde ich nur für das Zusammenhangskomponentenproblem in Detail gehen.