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.