Overview
Stoer-Wagner Min Cut applies merging weighted vertices while tracking the cheapest phase cut to handle global minimum cut with a named, inspectable procedure.
CoreSource checked
Stoer-Wagner Min Cut
Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Graph Cuts
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
global minimum cutgraph cutsheap ordergraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use Stoer-Wagner Min Cut when solving global minimum cut and you want to benefit from Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut.
- Choose it when O((V + E) log V) average/worst-case time and O(V + E) memory match your workload profile.
- Prefer it over Push-Relabel or Capacity Scaling Max Flow when the problem structure favors global minimum cut.
When Not to Use
- Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
- Avoid when a simpler traversal gives the same information with less bookkeeping.
What It Does
- Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut
- Organizes the work around global minimum cut and graph cuts.
Use Cases
- Production and research workloads requiring global minimum cut via Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut.
- Graph Cuts pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Push-Relabel and Capacity Scaling Max Flow when tuning global minimum cut.
Inputs
- Undirected edge-weighted graph G = (V, E, w)
Outputs
- Minimum cut value and vertex partition (S, V \ S) or cut-tree representation
Pseudocode
- 1.Construct the graph representation G = (V, E) and initialize auxiliary structures for global minimum cut (graph cuts).
- 2.Seed the initial frontier, partition, or residual capacities according to Stoer-Wagner Min Cut's invariants.
- 3.Iteratively process vertices or edges by Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut.
- 4.Maintain structural invariants (global minimum cut, graph cuts, heap order) and prune or contract resolved subproblems.
- 5.Extract and return the final global minimum cut structure from the converged graph state.
Canonical Example
- Input
- Undirected edge-weighted graph G = (V, E, w) configured for a representative global minimum cut test case
- Output
- Minimum cut value and vertex partition (S, V \ S) or cut-tree representation satisfying Stoer-Wagner Min Cut invariants
- Explanation
- Stoer-Wagner Min Cut processes the input by Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut, tracking global minimum cut and graph cuts to produce the verified global minimum cut result.
Implementation Notes
- Represent vertices and edges explicitly before optimizing storage.
- Keep graph direction, weights, and multiedges clear in tests.
- Record tie-breaking when multiple valid outputs exist.
Common Pitfalls
- Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
- Forgetting disconnected components or isolated vertices.
- Letting tie-breaking hide nondeterministic output in tests.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow merging weighted vertices while tracking the cheapest phase cut on a small global minimum cut example.
Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for global minimum cut (graph cuts).
graph-traversal-mechanismNotes
Stoer-Wagner Min Cut operates in O((V + E) log V) time and O(V + E) space within the Graph Cuts family. Often compared with Push-Relabel and Capacity Scaling Max Flow.
Sources (3)
What each reference supports for this entry.
Network Flows: Theory, Algorithms, and Applications
BookReference for Stoer-Wagner Min Cut's network-flow, cut, residual-network, or matching formulation.
Introduction to Algorithms (CLRS)
BookTextbook support for Stoer-Wagner Min Cut's algorithm family, complexity framing, and standard implementation concepts.
Open sourceStoer-Wagner Min Cut
PaperOriginal reference for the Stoer-Wagner global minimum cut algorithm using maximum adjacency search.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toPush-Relabel
Graph Traversal · Core
Both address global minimum cut, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toPush-Relabel
Both address global minimum cut, but they make different modeling or performance tradeoffs.
Alternative toCapacity Scaling Max Flow
Both address global minimum cut, but they make different modeling or performance tradeoffs.
Alternative toGomory-Hu Tree
Both address global minimum cut, but they make different modeling or performance tradeoffs.
Related Algorithms
Tags
GraphTraversalPriority Queue