# HG changeset patch # User Peter Kovacs # Date 1375760329 -7200 # Node ID c5cd8960df7431aceee364cceeedeafccafe3360 # Parent 218171dc022d194408f71d4dd290c5b0fb21dd44 Use m instead of e for denoting the number of arcs/edges (#463) diff -r 218171dc022d -r c5cd8960df74 doc/groups.dox --- a/doc/groups.dox Mon Aug 05 14:21:58 2013 +0200 +++ b/doc/groups.dox Tue Aug 06 05:38:49 2013 +0200 @@ -497,7 +497,7 @@ most efficient one, though the best known theoretical bound on its running time is exponential. Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms -run in time O(ne) and use space O(n2+e). +run in time O(nm) and use space O(n2+m). */ /** diff -r 218171dc022d -r c5cd8960df74 lemon/bellman_ford.h --- a/lemon/bellman_ford.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/bellman_ford.h Tue Aug 06 05:38:49 2013 +0200 @@ -149,7 +149,7 @@ /// \ingroup shortest_path /// This class provides an efficient implementation of the Bellman-Ford /// algorithm. The maximum time complexity of the algorithm is - /// O(ne). + /// O(nm). /// /// The Bellman-Ford algorithm solves the single-source shortest path /// problem when the arcs can have negative lengths, but the digraph diff -r 218171dc022d -r c5cd8960df74 lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/capacity_scaling.h Tue Aug 06 05:38:49 2013 +0200 @@ -69,7 +69,7 @@ /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, /// \cite edmondskarp72theoretical. It is an efficient dual /// solution method, which runs in polynomial time - /// \f$O(e\log U (n+e)\log n)\f$, where U denotes the maximum + /// \f$O(m\log U (n+m)\log n)\f$, where U denotes the maximum /// of node supply and arc capacity values. /// /// This algorithm is typically slower than \ref CostScaling and @@ -646,7 +646,7 @@ /// \brief Return the total cost of the found flow. /// /// This function returns the total cost of the found flow. - /// Its complexity is O(e). + /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a /// template parameter. For example, diff -r 218171dc022d -r c5cd8960df74 lemon/cost_scaling.h --- a/lemon/cost_scaling.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/cost_scaling.h Tue Aug 06 05:38:49 2013 +0200 @@ -97,7 +97,7 @@ /// can be viewed as the generalization of the \ref Preflow /// "preflow push-relabel" algorithm for the maximum flow problem. /// It is a polynomial algorithm, its running time complexity is - /// \f$O(n^2e\log(nK))\f$, where K denotes the maximum arc cost. + /// \f$O(n^2m\log(nK))\f$, where K denotes the maximum arc cost. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest /// implementations available in LEMON for solving this problem. @@ -670,7 +670,7 @@ /// \brief Return the total cost of the found flow. /// /// This function returns the total cost of the found flow. - /// Its complexity is O(e). + /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a /// template parameter. For example, diff -r 218171dc022d -r c5cd8960df74 lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/cycle_canceling.h Tue Aug 06 05:38:49 2013 +0200 @@ -51,7 +51,7 @@ /// \cite goldberg89cyclecanceling. /// The most efficent one is the \ref CANCEL_AND_TIGHTEN /// "Cancel-and-Tighten" algorithm, thus it is the default method. - /// It runs in strongly polynomial time O(n2e2log(n)), + /// It runs in strongly polynomial time O(n2m2log(n)), /// but in practice, it is typically orders of magnitude slower than /// the scaling algorithms and \ref NetworkSimplex. /// (For more information, see \ref min_cost_flow_algs "the module page".) @@ -133,13 +133,13 @@ /// well-known strongly polynomial method /// \cite goldberg89cyclecanceling. It improves along a /// \ref min_mean_cycle "minimum mean cycle" in each iteration. - /// Its running time complexity is O(n2e3log(n)). + /// Its running time complexity is O(n2m3log(n)). MINIMUM_MEAN_CYCLE_CANCELING, /// The "Cancel-and-Tighten" algorithm, which can be viewed as an /// improved version of the previous method /// \cite goldberg89cyclecanceling. /// It is faster both in theory and in practice, its running time - /// complexity is O(n2e2log(n)). + /// complexity is O(n2m2log(n)). CANCEL_AND_TIGHTEN }; @@ -576,7 +576,7 @@ /// \brief Return the total cost of the found flow. /// /// This function returns the total cost of the found flow. - /// Its complexity is O(e). + /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a /// template parameter. For example, diff -r 218171dc022d -r c5cd8960df74 lemon/gomory_hu.h --- a/lemon/gomory_hu.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/gomory_hu.h Tue Aug 06 05:38:49 2013 +0200 @@ -46,7 +46,7 @@ /// of nodes can easily be obtained. /// /// The algorithm calculates \e n-1 distinct minimum cuts (currently with - /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall + /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{m})\f$ overall /// time complexity. It calculates a rooted Gomory-Hu tree. /// The structure of the tree and the edge weights can be /// obtained using \c predNode(), \c predValue() and \c rootDist(). diff -r 218171dc022d -r c5cd8960df74 lemon/hartmann_orlin_mmc.h --- a/lemon/hartmann_orlin_mmc.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/hartmann_orlin_mmc.h Tue Aug 06 05:38:49 2013 +0200 @@ -102,7 +102,7 @@ /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but /// applies an early termination scheme. It makes the algorithm /// significantly faster for some problem instances, but slower for others. - /// The algorithm runs in time O(ne) and uses space O(n2+e). + /// The algorithm runs in time O(nm) and uses space O(n2+m). /// /// \tparam GR The type of the digraph the algorithm runs on. /// \tparam CM The type of the cost map. The default diff -r 218171dc022d -r c5cd8960df74 lemon/karp_mmc.h --- a/lemon/karp_mmc.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/karp_mmc.h Tue Aug 06 05:38:49 2013 +0200 @@ -99,7 +99,7 @@ /// This class implements Karp's algorithm for finding a directed /// cycle of minimum mean cost in a digraph /// \cite karp78characterization, \cite dasdan98minmeancycle. - /// It runs in time O(ne) and uses space O(n2+e). + /// It runs in time O(nm) and uses space O(n2+m). /// /// \tparam GR The type of the digraph the algorithm runs on. /// \tparam CM The type of the cost map. The default diff -r 218171dc022d -r c5cd8960df74 lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/min_cost_arborescence.h Tue Aug 06 05:38:49 2013 +0200 @@ -101,7 +101,7 @@ /// more sources should be given to the algorithm and it will calculate /// the minimum cost subgraph that is the union of arborescences with the /// given sources and spans all the nodes which are reachable from the - /// sources. The time complexity of the algorithm is O(n2+e). + /// sources. The time complexity of the algorithm is O(n2+m). /// /// The algorithm also provides an optimal dual solution, therefore /// the optimality of the solution can be checked. diff -r 218171dc022d -r c5cd8960df74 lemon/network_simplex.h --- a/lemon/network_simplex.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/network_simplex.h Tue Aug 06 05:38:49 2013 +0200 @@ -973,7 +973,7 @@ /// \brief Return the total cost of the found flow. /// /// This function returns the total cost of the found flow. - /// Its complexity is O(e). + /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a /// template parameter. For example, diff -r 218171dc022d -r c5cd8960df74 lemon/preflow.h --- a/lemon/preflow.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/preflow.h Tue Aug 06 05:38:49 2013 +0200 @@ -107,7 +107,7 @@ /// The preflow algorithms are the fastest known maximum /// flow algorithms. The current implementation uses a mixture of the /// \e "highest label" and the \e "bound decrease" heuristics. - /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. + /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{m})\f$. /// /// The algorithm consists of two phases. After the first phase /// the maximum flow value and the minimum cut is obtained. The diff -r 218171dc022d -r c5cd8960df74 lemon/suurballe.h --- a/lemon/suurballe.h Mon Aug 05 14:21:58 2013 +0200 +++ b/lemon/suurballe.h Tue Aug 06 05:38:49 2013 +0200 @@ -682,7 +682,7 @@ /// /// This function returns the total length of the found paths, i.e. /// the total cost of the found flow. - /// The complexity of the function is O(e). + /// The complexity of the function is O(m). /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function.