Context Navigation

Changeset 1080:c5cd8960df74 in lemon-main

Timestamp:

08/06/13 05:38:49 (11 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

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

Files:

r1053	r1080
498	498	time is exponential.
499	499	Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
500		run in time O(n~~e) and use space O(n<sup>2</sup>+e~~).
	500	run in time O(nm) and use space O(n<sup>2</sup>+m).
501	501	*/
502	502

r1074	r1080
150	150	/// This class provides an efficient implementation of the Bellman-Ford
151	151	/// algorithm. The maximum time complexity of the algorithm is
152		/// <tt>O(ne)</tt>.
	152	/// <tt>O(nm)</tt>.
153	153	///
154	154	/// The Bellman-Ford algorithm solves the single-source shortest path

-                      r1074
+                      r1080
   /// \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 <i>U</i> denotes the maximum
+  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> 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

-                      r1074
+                      r1080
   /// "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 <i>K</i> denotes the maximum arc cost.
+  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> 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

-                      r1071
+                      r1080
   /// 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(n<sup>2</sup>e<sup>2</sup>log(n)),
+  /// It runs in strongly polynomial time O(n<sup>2</sup>m<sup>2</sup>log(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(n<sup>2</sup>e<sup>3</sup>log(n)).
+      /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(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(n<sup>2</sup>e<sup>2</sup>log(n)).
+      /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(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

r877	r1080
47	47	///
48	48	/// The algorithm calculates \e n-1 distinct minimum cuts (currently with
49		/// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
	49	/// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{m})\f$ overall
50	50	/// time complexity. It calculates a rooted Gomory-Hu tree.
51	51	/// The structure of the tree and the edge weights can be

r1074	r1080
103	103	/// applies an early termination scheme. It makes the algorithm
104	104	/// significantly faster for some problem instances, but slower for others.
105		/// The algorithm runs in time O(n~~e) and uses space O(n<sup>2</sup>+e~~).
	105	/// The algorithm runs in time O(nm) and uses space O(n<sup>2</sup>+m).
106	106	///
107	107	/// \tparam GR The type of the digraph the algorithm runs on.

r1074	r1080
100	100	/// cycle of minimum mean cost in a digraph
101	101	/// \cite karp78characterization, \cite dasdan98minmeancycle.
102		/// It runs in time O(n~~e) and uses space O(n<sup>2</sup>+e~~).
	102	/// It runs in time O(nm) and uses space O(n<sup>2</sup>+m).
103	103	///
104	104	/// \tparam GR The type of the digraph the algorithm runs on.

r1074	r1080
102	102	/// the minimum cost subgraph that is the union of arborescences with the
103	103	/// given sources and spans all the nodes which are reachable from the
104		/// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
	104	/// sources. The time complexity of the algorithm is O(n<sup>2</sup>+m).
105	105	///
106	106	/// The algorithm also provides an optimal dual solution, therefore

r1071	r1080
974	974	///
975	975	/// This function returns the total cost of the found flow.
976		/// Its complexity is O(e).
	976	/// Its complexity is O(m).
977	977	///
978	978	/// \note The return type of the function can be specified as a

r1074	r1080
108	108	/// flow algorithms. The current implementation uses a mixture of the
109	109	/// \e "highest label" and the \e "bound decrease" heuristics.
110		/// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
	110	/// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{m})\f$.
111	111	///
112	112	/// The algorithm consists of two phases. After the first phase

r1074	r1080
683	683	/// This function returns the total length of the found paths, i.e.
684	684	/// the total cost of the found flow.
685		/// The complexity of the function is O(e).
	685	/// The complexity of the function is O(m).
686	686	///
687	687	/// \pre \ref run() or \ref findFlow() must be called before using

Note: See TracChangeset for help on using the changeset viewer.