doc/groups.dox
 changeset 1023 e0cef67fe565 parent 999 c279b19abc62 child 1164 f63ba40a60f4
equal inserted replaced
55:87616ba6048f 56:b8f77ff22011
   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.