Library of Efficient Datatypes and Algorithms
LEP: KCUT
     We are given an undirected graph G with non-negative edge weights. A k-cut is a set C of edges such that G\C has at least k components. The weight of a cut is the sum of the weight of its edges. The LEP KCUT computes a minimum k-cut.
Download Software 
Download Documentation 
Contact 
 Kurt Mehlhorn 
Max-Planck-Institut für Informatik 
Algorithms and Complexity Group (AG1) 
Stuhlsatzenhausweg 85 
66123 Saarbrücken
Germany 
email: mehlhorn@mpi-sb.mpg.de 
     
Bibliography 
  • The LEDA Platform for Combinatorial and Geometric Computing

    • K.Mehlhorn and S.Naeher
    Cambridge University Press, 1999. 1018 pages,
  • Finding k cuts within twice the optimal

    • Huzur Saran and Vijay V. Vazirani
    in: Siam Journal on Computing, 23(1):101-108, February 1995,
  • A simple min-cut algorithm

    • M. Stoer and F. Wagner
    in: Journal of the ACM, 44(4):585-591, July 1997

back to LEP page back to the LEDA EP index page
person responsible for the page: Michael Seel