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

Main titleA simple min cut algorithm
AuthorStoer, Mechtild
AuthorWagner, Frank
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages8 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,12
Classification (DDC)004 Data processing and Computer science
AbstractWe 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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1994
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-13 : 02:36:16
Last changed2015-02-27 : 08:24:52
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001146