Merge #463
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 06 Aug 2013 17:58:59 +0200
changeset 1082cae19e9eeca4
parent 1079 5958cc5c0a98
parent 1081 9d1616d708ee
child 1086 97f1760dcd13
Merge #463
     1.1 --- a/doc/groups.dox	Tue Aug 06 12:28:37 2013 +0200
     1.2 +++ b/doc/groups.dox	Tue Aug 06 17:58:59 2013 +0200
     1.3 @@ -497,7 +497,7 @@
     1.4  most efficient one, though the best known theoretical bound on its running
     1.5  time is exponential.
     1.6  Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     1.7 -run in time O(ne) and use space O(n<sup>2</sup>+e).
     1.8 +run in time O(nm) and use space O(n<sup>2</sup>+m).
     1.9  */
    1.10  
    1.11  /**
     2.1 --- a/lemon/bellman_ford.h	Tue Aug 06 12:28:37 2013 +0200
     2.2 +++ b/lemon/bellman_ford.h	Tue Aug 06 17:58:59 2013 +0200
     2.3 @@ -149,7 +149,7 @@
     2.4    /// \ingroup shortest_path
     2.5    /// This class provides an efficient implementation of the Bellman-Ford
     2.6    /// algorithm. The maximum time complexity of the algorithm is
     2.7 -  /// <tt>O(ne)</tt>.
     2.8 +  /// <tt>O(nm)</tt>.
     2.9    ///
    2.10    /// The Bellman-Ford algorithm solves the single-source shortest path
    2.11    /// problem when the arcs can have negative lengths, but the digraph
     3.1 --- a/lemon/capacity_scaling.h	Tue Aug 06 12:28:37 2013 +0200
     3.2 +++ b/lemon/capacity_scaling.h	Tue Aug 06 17:58:59 2013 +0200
     3.3 @@ -69,7 +69,7 @@
     3.4    /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     3.5    /// \cite edmondskarp72theoretical. It is an efficient dual
     3.6    /// solution method, which runs in polynomial time
     3.7 -  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
     3.8 +  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     3.9    /// of node supply and arc capacity values.
    3.10    ///
    3.11    /// This algorithm is typically slower than \ref CostScaling and
    3.12 @@ -646,7 +646,7 @@
    3.13      /// \brief Return the total cost of the found flow.
    3.14      ///
    3.15      /// This function returns the total cost of the found flow.
    3.16 -    /// Its complexity is O(e).
    3.17 +    /// Its complexity is O(m).
    3.18      ///
    3.19      /// \note The return type of the function can be specified as a
    3.20      /// template parameter. For example,
     4.1 --- a/lemon/cost_scaling.h	Tue Aug 06 12:28:37 2013 +0200
     4.2 +++ b/lemon/cost_scaling.h	Tue Aug 06 17:58:59 2013 +0200
     4.3 @@ -97,7 +97,7 @@
     4.4    /// can be viewed as the generalization of the \ref Preflow
     4.5    /// "preflow push-relabel" algorithm for the maximum flow problem.
     4.6    /// It is a polynomial algorithm, its running time complexity is
     4.7 -  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
     4.8 +  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
     4.9    ///
    4.10    /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    4.11    /// implementations available in LEMON for solving this problem.
    4.12 @@ -670,7 +670,7 @@
    4.13      /// \brief Return the total cost of the found flow.
    4.14      ///
    4.15      /// This function returns the total cost of the found flow.
    4.16 -    /// Its complexity is O(e).
    4.17 +    /// Its complexity is O(m).
    4.18      ///
    4.19      /// \note The return type of the function can be specified as a
    4.20      /// template parameter. For example,
     5.1 --- a/lemon/cycle_canceling.h	Tue Aug 06 12:28:37 2013 +0200
     5.2 +++ b/lemon/cycle_canceling.h	Tue Aug 06 17:58:59 2013 +0200
     5.3 @@ -51,7 +51,7 @@
     5.4    /// \cite goldberg89cyclecanceling.
     5.5    /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
     5.6    /// "Cancel-and-Tighten" algorithm, thus it is the default method.
     5.7 -  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
     5.8 +  /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$,
     5.9    /// but in practice, it is typically orders of magnitude slower than
    5.10    /// the scaling algorithms and \ref NetworkSimplex.
    5.11    /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5.12 @@ -133,13 +133,13 @@
    5.13        /// well-known strongly polynomial method
    5.14        /// \cite goldberg89cyclecanceling. It improves along a
    5.15        /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    5.16 -      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
    5.17 +      /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$.
    5.18        MINIMUM_MEAN_CYCLE_CANCELING,
    5.19        /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    5.20        /// improved version of the previous method
    5.21        /// \cite goldberg89cyclecanceling.
    5.22        /// It is faster both in theory and in practice, its running time
    5.23 -      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
    5.24 +      /// complexity is \f$O(n^2 m^2 \log n)\f$.
    5.25        CANCEL_AND_TIGHTEN
    5.26      };
    5.27  
    5.28 @@ -576,7 +576,7 @@
    5.29      /// \brief Return the total cost of the found flow.
    5.30      ///
    5.31      /// This function returns the total cost of the found flow.
    5.32 -    /// Its complexity is O(e).
    5.33 +    /// Its complexity is O(m).
    5.34      ///
    5.35      /// \note The return type of the function can be specified as a
    5.36      /// template parameter. For example,
     6.1 --- a/lemon/gomory_hu.h	Tue Aug 06 12:28:37 2013 +0200
     6.2 +++ b/lemon/gomory_hu.h	Tue Aug 06 17:58:59 2013 +0200
     6.3 @@ -46,7 +46,7 @@
     6.4    /// of nodes can easily be obtained.
     6.5    ///
     6.6    /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
     6.7 -  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     6.8 +  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{m})\f$ overall
     6.9    /// time complexity. It calculates a rooted Gomory-Hu tree.
    6.10    /// The structure of the tree and the edge weights can be
    6.11    /// obtained using \c predNode(), \c predValue() and \c rootDist().
     7.1 --- a/lemon/hartmann_orlin_mmc.h	Tue Aug 06 12:28:37 2013 +0200
     7.2 +++ b/lemon/hartmann_orlin_mmc.h	Tue Aug 06 17:58:59 2013 +0200
     7.3 @@ -102,7 +102,7 @@
     7.4    /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
     7.5    /// applies an early termination scheme. It makes the algorithm
     7.6    /// significantly faster for some problem instances, but slower for others.
     7.7 -  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     7.8 +  /// The algorithm runs in time O(nm) and uses space O(n<sup>2</sup>+m).
     7.9    ///
    7.10    /// \tparam GR The type of the digraph the algorithm runs on.
    7.11    /// \tparam CM The type of the cost map. The default
     8.1 --- a/lemon/karp_mmc.h	Tue Aug 06 12:28:37 2013 +0200
     8.2 +++ b/lemon/karp_mmc.h	Tue Aug 06 17:58:59 2013 +0200
     8.3 @@ -99,7 +99,7 @@
     8.4    /// This class implements Karp's algorithm for finding a directed
     8.5    /// cycle of minimum mean cost in a digraph
     8.6    /// \cite karp78characterization, \cite dasdan98minmeancycle.
     8.7 -  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     8.8 +  /// It runs in time O(nm) and uses space O(n<sup>2</sup>+m).
     8.9    ///
    8.10    /// \tparam GR The type of the digraph the algorithm runs on.
    8.11    /// \tparam CM The type of the cost map. The default
     9.1 --- a/lemon/min_cost_arborescence.h	Tue Aug 06 12:28:37 2013 +0200
     9.2 +++ b/lemon/min_cost_arborescence.h	Tue Aug 06 17:58:59 2013 +0200
     9.3 @@ -101,7 +101,7 @@
     9.4    /// more sources should be given to the algorithm and it will calculate
     9.5    /// the minimum cost subgraph that is the union of arborescences with the
     9.6    /// given sources and spans all the nodes which are reachable from the
     9.7 -  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
     9.8 +  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+m).
     9.9    ///
    9.10    /// The algorithm also provides an optimal dual solution, therefore
    9.11    /// the optimality of the solution can be checked.
    10.1 --- a/lemon/network_simplex.h	Tue Aug 06 12:28:37 2013 +0200
    10.2 +++ b/lemon/network_simplex.h	Tue Aug 06 17:58:59 2013 +0200
    10.3 @@ -973,7 +973,7 @@
    10.4      /// \brief Return the total cost of the found flow.
    10.5      ///
    10.6      /// This function returns the total cost of the found flow.
    10.7 -    /// Its complexity is O(e).
    10.8 +    /// Its complexity is O(m).
    10.9      ///
   10.10      /// \note The return type of the function can be specified as a
   10.11      /// template parameter. For example,
    11.1 --- a/lemon/preflow.h	Tue Aug 06 12:28:37 2013 +0200
    11.2 +++ b/lemon/preflow.h	Tue Aug 06 17:58:59 2013 +0200
    11.3 @@ -107,7 +107,7 @@
    11.4    /// The preflow algorithms are the fastest known maximum
    11.5    /// flow algorithms. The current implementation uses a mixture of the
    11.6    /// \e "highest label" and the \e "bound decrease" heuristics.
    11.7 -  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    11.8 +  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{m})\f$.
    11.9    ///
   11.10    /// The algorithm consists of two phases. After the first phase
   11.11    /// the maximum flow value and the minimum cut is obtained. The
    12.1 --- a/lemon/suurballe.h	Tue Aug 06 12:28:37 2013 +0200
    12.2 +++ b/lemon/suurballe.h	Tue Aug 06 17:58:59 2013 +0200
    12.3 @@ -682,7 +682,7 @@
    12.4      ///
    12.5      /// This function returns the total length of the found paths, i.e.
    12.6      /// the total cost of the found flow.
    12.7 -    /// The complexity of the function is O(e).
    12.8 +    /// The complexity of the function is O(m).
    12.9      ///
   12.10      /// \pre \ref run() or \ref findFlow() must be called before using
   12.11      /// this function.