1.1 --- a/lemon/min_cut.h Fri Sep 29 11:26:29 2006 +0000
1.2 +++ b/lemon/min_cut.h Fri Sep 29 11:36:30 2006 +0000
1.3 @@ -830,18 +830,19 @@
1.4
1.5 /// \ingroup topology
1.6 ///
1.7 - /// \brief Calculates the min cut in an undirected graph.
1.8 + /// \brief Calculates the minimum cut in an undirected graph.
1.9 ///
1.10 - /// Calculates the min cut in an undirected graph.
1.11 - /// The algorithm separates the graph's nodes into two partitions with the
1.12 - /// min sum of edge capacities between the two partitions. The
1.13 - /// algorithm can be used to test the network reliability specifically
1.14 - /// to test how many links have to be destroyed in the network to split it
1.15 - /// at least two distinict subnetwork.
1.16 + /// Calculates the minimum cut in an undirected graph with the
1.17 + /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
1.18 + /// nodes into two partitions with the minimum sum of edge capacities
1.19 + /// between the two partitions. The algorithm can be used to test
1.20 + /// the network reliability specifically to test how many links have
1.21 + /// to be destroyed in the network to split it at least two
1.22 + /// distinict subnetwork.
1.23 ///
1.24 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
1.25 - /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
1.26 - /// the neutral capacity map is used then it uses BucketHeap which
1.27 + /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
1.28 + /// \f$. When capacity map is neutral then it uses BucketHeap which
1.29 /// results \f$ O(ne) \f$ time complexity.
1.30 #ifdef DOXYGEN
1.31 template <typename _Graph, typename _CapacityMap, typename _Traits>