TheAlgorithms
Add store wanger
Overview This implementation defines the Stoer-Wagner algorithm in R for computing the global minimum cut of an undirected weighted graph. The algorithm identifies the smallest set of edges whose removal disconnects the graph, making it useful for network reliability, graph clustering, and partitioning tasks.
Features
Finds the global minimum cut in undirected weighted graphs. Works with connected graphs and non-negative edge weights. Uses a greedy iterative approach by merging vertices and tracking cut weights. Returns the minimum cut weight and can be extended to output vertex partitions. Includes example adjacency matrix for demonstration. Can be applied to small and medium-sized graphs efficiently.
Complexity
Time Complexity: O(V³) for dense graphs (V = number of vertices)
Space Complexity: O(V²) for storing the adjacency/weight matrix
Demonstration
The included R script computes the minimum cut on a 4-vertex weighted undirected graph. Prints the minimum cut weight. Users can replace the adjacency matrix with their own graph data to compute minimum cuts.
Summary This implementation adds the Stoer-Wagner minimum cut algorithm to the R algorithms repository. It is suitable for network reliability analysis, graph clustering, and identifying critical edges in weighted undirected networks.
