diff -r e344f0887c59 -r d59484d5fc1f doc/groups.dox --- a/doc/groups.dox Thu Sep 13 12:23:46 2012 +0200 +++ b/doc/groups.dox Wed Nov 07 17:39:39 2012 +0100 @@ -407,9 +407,19 @@ strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general, \ref NetworkSimplex and \ref CostScaling are the most efficient -implementations, but the other two algorithms could be faster in special cases. +implementations. +\ref NetworkSimplex is usually the fastest on relatively small graphs (up to +several thousands of nodes) and on dense graphs, while \ref CostScaling is +typically more efficient on large graphs (e.g. hundreds of thousands of +nodes or above), especially if they are sparse. +However, other algorithms could be faster in special cases. For example, if the total supply and/or capacities are rather small, \ref CapacityScaling is usually the fastest algorithm (without effective scaling). + +These classes are intended to be used with integer-valued input data +(capacities, supply values, and costs), except for \ref CapacityScaling, +which is capable of handling real-valued arc costs (other numerical +data are required to be integer). */ /** @@ -448,7 +458,7 @@ \brief Algorithms for finding minimum mean cycles. This group contains the algorithms for finding minimum mean cycles -\ref clrs01algorithms, \ref amo93networkflows. +\ref amo93networkflows, \ref karp78characterization. The \e minimum \e mean \e cycle \e problem is to find a directed cycle of minimum mean length (cost) in a digraph. @@ -464,12 +474,11 @@ function. LEMON contains three algorithms for solving the minimum mean cycle problem: -- \ref KarpMmc Karp's original algorithm \ref amo93networkflows, - \ref dasdan98minmeancycle. +- \ref KarpMmc Karp's original algorithm \ref karp78characterization. - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved - version of Karp's algorithm \ref dasdan98minmeancycle. + version of Karp's algorithm \ref hartmann93finding. - \ref HowardMmc Howard's policy iteration algorithm - \ref dasdan98minmeancycle. + \ref dasdan98minmeancycle, \ref dasdan04experimental. In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the most efficient one, though the best known theoretical bound on its running