dc.contributor.author
Stoer, Mechtild
dc.contributor.author
Wagner, Frank
dc.date.accessioned
2018-06-08T07:46:48Z
dc.date.available
2009-03-13T14:36:16.365Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/18688
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-22375
dc.description.abstract
We 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.
en
dc.relation.ispartofseries
urn:nbn:de:kobv:188-fudocsseries000000000021-2
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
A simple min cut algorithm
refubium.affiliation
Mathematik und Informatik
de
refubium.affiliation.other
Institut für Informatik
![Dieser Wert wurde niemals validiert.](/cache_202e45ad85b55efaeb29160f63cd3f3b/themes/FuCD/images/authority_control/invisible.gif)
refubium.mycore.fudocsId
FUDOCS_document_000000001146
refubium.resourceType.isindependentpub
no
refubium.series.name
Freie Universität Berlin, Fachbereich Mathematik und Informatik
refubium.series.reportNumber
94-12
refubium.mycore.derivateId
FUDOCS_derivate_000000000270
dcterms.accessRights.openaire
open access