389 If you want to find minimum cut just between two distinict nodes, |
389 If you want to find minimum cut just between two distinict nodes, |
390 see the \ref max_flow "maximum flow problem". |
390 see the \ref max_flow "maximum flow problem". |
391 */ |
391 */ |
392 |
392 |
393 /** |
393 /** |
|
394 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms |
|
395 @ingroup algs |
|
396 \brief Algorithms for finding minimum mean cycles. |
|
397 |
|
398 This group contains the algorithms for finding minimum mean cycles. |
|
399 |
|
400 The \e minimum \e mean \e cycle \e problem is to find a directed cycle |
|
401 of minimum mean length (cost) in a digraph. |
|
402 The mean length of a cycle is the average length of its arcs, i.e. the |
|
403 ratio between the total length of the cycle and the number of arcs on it. |
|
404 |
|
405 This problem has an important connection to \e conservative \e length |
|
406 \e functions, too. A length function on the arcs of a digraph is called |
|
407 conservative if and only if there is no directed cycle of negative total |
|
408 length. For an arbitrary length function, the negative of the minimum |
|
409 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
|
410 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
|
411 function. |
|
412 |
|
413 LEMON contains three algorithms for solving the minimum mean cycle problem: |
|
414 - \ref Karp "Karp"'s original algorithm. |
|
415 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved |
|
416 version of Karp's algorithm. |
|
417 - \ref Howard "Howard"'s policy iteration algorithm. |
|
418 |
|
419 In practice, the Howard algorithm proved to be by far the most efficient |
|
420 one, though the best known theoretical bound on its running time is |
|
421 exponential. |
|
422 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
|
423 O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
|
424 applied early termination scheme. |
|
425 */ |
|
426 |
|
427 /** |
394 @defgroup graph_properties Connectivity and Other Graph Properties |
428 @defgroup graph_properties Connectivity and Other Graph Properties |
395 @ingroup algs |
429 @ingroup algs |
396 \brief Algorithms for discovering the graph properties |
430 \brief Algorithms for discovering the graph properties |
397 |
431 |
398 This group contains the algorithms for discovering the graph properties |
432 This group contains the algorithms for discovering the graph properties |