Changeset 2225:bb3d5e6f9fcb in lemon0.x for lemon/min_cut.h
 Timestamp:
 09/29/06 13:36:30 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2965
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/min_cut.h
r2176 r2225 831 831 /// \ingroup topology 832 832 /// 833 /// \brief Calculates the min cut in an undirected graph.833 /// \brief Calculates the minimum cut in an undirected graph. 834 834 /// 835 /// Calculates the min cut in an undirected graph. 836 /// The algorithm separates the graph's nodes into two partitions with the 837 /// min sum of edge capacities between the two partitions. The 838 /// algorithm can be used to test the network reliability specifically 839 /// to test how many links have to be destroyed in the network to split it 840 /// at least two distinict subnetwork. 835 /// Calculates the minimum cut in an undirected graph with the 836 /// NagamochiIbaraki algorithm. The algorithm separates the graph's 837 /// nodes into two partitions with the minimum sum of edge capacities 838 /// between the two partitions. The algorithm can be used to test 839 /// the network reliability specifically to test how many links have 840 /// to be destroyed in the network to split it at least two 841 /// distinict subnetwork. 841 842 /// 842 843 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with 843 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When844 /// the neutral capacity map is usedthen it uses BucketHeap which844 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) 845 /// \f$. When capacity map is neutral then it uses BucketHeap which 845 846 /// results \f$ O(ne) \f$ time complexity. 846 847 #ifdef DOXYGEN
Note: See TracChangeset
for help on using the changeset viewer.