A Simple Hypergraph Min Cut Algorithm

Regina Klimmek
Fachbereich Mathematik
Technische Universität Berlin
Straße des 17. Juni 135
10623 Berlin, Germany

Frank Wagner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: wagner@inf.fu-berlin.de

Report B 96-02
March 1996

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-96-02.ps.gz
A Simple Hypergraph Min Cut Algorithm We present an algorithm for finding the minimum cut of an edge-weighted hypergraph. 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. The runtime is $\bigO(|V|^2\log |V| + |V|\cdot||E||)$ where $||E||$ is the sum of the cardinalities of the hyperedges.