The Stoer-Wagner algorithm is a recursive algorithm that solves the minimum cut problem in undirected weighted graphs with non-negative weights, proposed by Mechthild Stoer and Frank Wagner in 1995. It works by repeatedly shrinking the graph, merging its most tightly connected vertices in each phase until only two combined vertex sets remain, finding a minimum cut between two chosen vertices at each phase and keeping the lightest such cut found across all phases as the global minimum cut.
Facts
Time Complexity
Time Complexity (category) Connections
In Field
Source Stoer-Wagner algorithm (Wikipedia)
Uses Design Technique
Source Stoer-Wagner algorithm (Wikipedia)
Sources
1. Stoer-Wagner Algorithm (Wikipedia)
Wikipedia infobox: time complexity cubicQuote, Wikipedia infobox: time complexity cubic
cubic
Stoer-Wagner algorithm (Wikipedia)
Uses Design Technique: Recursion, Lead
In graph theory, the Stoer-Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights.
In Field: Algorithms and Complexity Theory, Lead sentence
Stoer-Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights.
In Group: Network Flow and Matching Algorithms, Lead
In graph theory, the Stoer-Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.