#
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.