Karger's algorithm
id:
karger-s-algorithm-270-12715848
title:
Karger's algorithm
text:
In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993. The idea of the algorithm is based on the concept of contraction of an edge in an undirected graph G = . Informally speaking, the contraction of an edge merges the nodes u and v into one, reducing the total number of nodes of the graph by one. All other edges connecting either u or v are "reattached" to the
brand slug:
wiki
category slug:
encyclopedia
description:
Randomized algorithm for minimum cuts
original url:
https://en.wikipedia.org/wiki/Karger%27s_algorithm
date created:
date modified:
2024-02-16T07:17:34Z
main entity:
{"identifier":"Q4924414","url":"https://www.wikidata.org/entity/Q4924414"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/c/c0/Min_cut_example.svg","width":265,"height":206}
fields total:
13
integrity:
15