The Minimum Cut Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
=Algorithms= | =Algorithms= | ||
==Karger's Contraction Algorithm== | ==Karger's Contraction Algorithm== | ||
Karger's Contraction Algorithm is an example of a [[Randomized_Algorithms#Overview|randomized algorithm]]. | |||
{{Internal|Karger%27s_Contraction_Algorithm#Overview|Karger's Contraction Algorithm}} | {{Internal|Karger%27s_Contraction_Algorithm#Overview|Karger's Contraction Algorithm}} | ||
Latest revision as of 22:53, 20 October 2021
Internal
Overview
Given an undirected graph G = (V, E), compute a cut with the fewest number of crossing edges.
Applications:
- identify network bottleneck or weaknesses
- community detection in social networks
- image segmentation
Algorithms
Karger's Contraction Algorithm
Karger's Contraction Algorithm is an example of a randomized algorithm.