Skip to content

LisaLentati/KargerAlgorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 

Repository files navigation

Implementation of Karger's randomised algorithm for finding a minimum cut in a graph

The implemented algorithm outputs a minimum cut with an error probability of at most 0.01.

To run the algorithm write on the cmd line

java RMinCut v1 v2 v2 v3 v5 v4 ...

where each argument is an integer and the arguments are processed in pairs to indicate the edges of the input graph: that is, the edges of the graph are {v1, v2}, {v2, v3}, {v5, v4} and so on.

More info on the algorithm: https://en.wikipedia.org/wiki/Karger%27s_algorithm

About

Implementation of Karger's algorithm

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages