lemon/cycle_canceling.h
changeset 1055 05b34170866b
parent 1049 7bf489cf624e
child 1071 879fcb781086
equal deleted inserted replaced
14:934155b259cc 15:4834e3340ae6
    45   /// \brief Implementation of cycle-canceling algorithms for
    45   /// \brief Implementation of cycle-canceling algorithms for
    46   /// finding a \ref min_cost_flow "minimum cost flow".
    46   /// finding a \ref min_cost_flow "minimum cost flow".
    47   ///
    47   ///
    48   /// \ref CycleCanceling implements three different cycle-canceling
    48   /// \ref CycleCanceling implements three different cycle-canceling
    49   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    49   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    50   /// \ref amo93networkflows, \ref klein67primal,
    50   /// \cite amo93networkflows, \cite klein67primal,
    51   /// \ref goldberg89cyclecanceling.
    51   /// \cite goldberg89cyclecanceling.
    52   /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    52   /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    53   /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    53   /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
    54   /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
    55   /// but in practice, it is typically orders of magnitude slower than
    55   /// but in practice, it is typically orders of magnitude slower than
    56   /// the scaling algorithms and \ref NetworkSimplex.
    56   /// the scaling algorithms and \ref NetworkSimplex.
   129       /// The number of Bellman-Ford iterations is bounded by a successively
   129       /// The number of Bellman-Ford iterations is bounded by a successively
   130       /// increased limit.
   130       /// increased limit.
   131       SIMPLE_CYCLE_CANCELING,
   131       SIMPLE_CYCLE_CANCELING,
   132       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
   132       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
   133       /// well-known strongly polynomial method
   133       /// well-known strongly polynomial method
   134       /// \ref goldberg89cyclecanceling. It improves along a
   134       /// \cite goldberg89cyclecanceling. It improves along a
   135       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
   135       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
   136       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
   136       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
   137       MINIMUM_MEAN_CYCLE_CANCELING,
   137       MINIMUM_MEAN_CYCLE_CANCELING,
   138       /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
   138       /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
   139       /// improved version of the previous method
   139       /// improved version of the previous method
   140       /// \ref goldberg89cyclecanceling.
   140       /// \cite goldberg89cyclecanceling.
   141       /// It is faster both in theory and in practice, its running time
   141       /// It is faster both in theory and in practice, its running time
   142       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
   142       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
   143       CANCEL_AND_TIGHTEN
   143       CANCEL_AND_TIGHTEN
   144     };
   144     };
   145 
   145