equal
deleted
inserted
replaced
404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive |
404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive |
405 shortest path method \ref edmondskarp72theoretical. |
405 shortest path method \ref edmondskarp72theoretical. |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
408 |
408 |
409 In general NetworkSimplex is the most efficient implementation, |
409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient |
410 but in special cases other algorithms could be faster. |
410 implementations, but the other two algorithms could be faster in special cases. |
411 For example, if the total supply and/or capacities are rather small, |
411 For example, if the total supply and/or capacities are rather small, |
412 CapacityScaling is usually the fastest algorithm (without effective scaling). |
412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). |
413 */ |
413 */ |
414 |
414 |
415 /** |
415 /** |
416 @defgroup min_cut Minimum Cut Algorithms |
416 @defgroup min_cut Minimum Cut Algorithms |
417 @ingroup algs |
417 @ingroup algs |
469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
470 version of Karp's algorithm \ref dasdan98minmeancycle. |
470 version of Karp's algorithm \ref dasdan98minmeancycle. |
471 - \ref HowardMmc Howard's policy iteration algorithm |
471 - \ref HowardMmc Howard's policy iteration algorithm |
472 \ref dasdan98minmeancycle. |
472 \ref dasdan98minmeancycle. |
473 |
473 |
474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the |
474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the |
475 most efficient one, though the best known theoretical bound on its running |
475 most efficient one, though the best known theoretical bound on its running |
476 time is exponential. |
476 time is exponential. |
477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is |
478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is |
479 typically faster due to the applied early termination scheme. |
479 typically faster due to the applied early termination scheme. |
537 \image html connected_components.png |
537 \image html connected_components.png |
538 \image latex connected_components.eps "Connected components" width=\textwidth |
538 \image latex connected_components.eps "Connected components" width=\textwidth |
539 */ |
539 */ |
540 |
540 |
541 /** |
541 /** |
542 @defgroup planar Planarity Embedding and Drawing |
542 @defgroup planar Planar Embedding and Drawing |
543 @ingroup algs |
543 @ingroup algs |
544 \brief Algorithms for planarity checking, embedding and drawing |
544 \brief Algorithms for planarity checking, embedding and drawing |
545 |
545 |
546 This group contains the algorithms for planarity checking, |
546 This group contains the algorithms for planarity checking, |
547 embedding and drawing. |
547 embedding and drawing. |