karger_example.cc File Reference

Comprehensive educational example for Karger's min-cut algorithm. More...

#include <iostream>
#include <Karger.H>
#include <tpl_graph.H>

Include dependency graph for karger_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Comprehensive educational example for Karger's min-cut algorithm.

WHAT IS A MIN-CUT?

A minimum cut of a graph is a partition of vertices into two non-empty sets such that the number of edges crossing between the sets is minimized.

WHY IS IT IMPORTANT?

• Network reliability: Find critical connections (bridges)
• Graph clustering: Partition graphs into communities
• VLSI design: Minimize wire crossings
• Image segmentation: Partition image into regions

KARGER'S ALGORITHM:

Randomized algorithm that repeatedly contracts random edges until only two "super-nodes" remain. The edges between them form a cut.

• Time: O(n^2 * m) per iteration
• Success probability: >= 1/n^2 per iteration
• Running O(n^2 log n) iterations gives high probability of success
• Fast variant (Karger-Stein): O(n^2 log^3 n)

COMPILE & RUN:

g++ -std=c++20 -I.. -o karger_example karger_example.cc -lgsl -lgslcblas ./karger_example

Definition in file karger_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 40 of file karger_example.cc.

References Aleph::maps().