Library of Efficient Datatypes and Algorithms
LEP: Minimum Mean Cycle
     We are given a directed graph G in which every edge e has a weight c(e) associated with it; weights may be negative. A minimum mean cycle is a cycle C that minimizes c(C)/|C|.
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,
  • Faster parametric shortest path and minimum-balance algorithms

    • N. E. Young, Robert E. Tarjan and J. B. Orlin
    in: Networks, 21:205-221, 1991

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