Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

A simple min cut algorithm
Stoer, Mechtild ;  Wagner, Frank ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelA simple min cut algorithm
AutorStoer, Mechtild
AutorWagner, Frank
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl8 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,12
DDC004 Datenverarbeitung; Informatik
ZusammenfassungWe present an algorithm for finding the minimum cut of an edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement and has a surprisingly simple proof of correctness. Its runtime matches that of the fastest algorithm known. The runtime analysis is straightforward. In contrast to nearly all approaches so far, the algorithm uses no flow techniques. Roughly spoken the algorithm consists of about |V| nearly identical phases each of which is formally similar to Prim's minimum spanning tree algorithm.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1994
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am13.03.2009 - 14:36:16
Letzte Änderung23.01.2014 - 16:21:15
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001146
Zugriffsstatistik
 

LOADING...