The Minimum Cut Problem: Difference between revisions
Jump to navigation
Jump to search
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Graph_Concepts#The_Minimum_Cut_Problem|Graph Concepts]] | * [[Graph_Concepts#The_Minimum_Cut_Problem|Graph Concepts]] | ||
=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= | =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.