# Changeset 1254:c5cd8960df74 in lemon

Ignore:
Timestamp:
08/06/13 05:38:49 (7 years ago)
Branch:
default
Phase:
public
Message:

Use m instead of e for denoting the number of arcs/edges (#463)

Files:
12 edited

Unmodified
Removed
• ## doc/groups.dox

 r1221 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). */
• ## lemon/bellman_ford.h

 r1250 /// 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
• ## lemon/capacity_scaling.h

 r1250 /// \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 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
• ## lemon/cost_scaling.h

 r1250 /// "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 /// /// 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
• ## lemon/cycle_canceling.h

 r1241 /// 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. /// \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 /// \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 }; /// /// 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
• ## lemon/gomory_hu.h

 r956 /// /// 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
• ## lemon/hartmann_orlin_mmc.h

 r1250 /// 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.
• ## lemon/karp_mmc.h

 r1250 /// 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.
• ## lemon/min_cost_arborescence.h

 r1250 /// 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
• ## lemon/network_simplex.h

 r1241 /// /// 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
• ## lemon/preflow.h

 r1250 /// 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
• ## lemon/suurballe.h

 r1250 /// 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
Note: See TracChangeset for help on using the changeset viewer.