Karger's algorithm
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 . Informally speaking, the contraction of an edge merges the nodes and into one, reducing the total number of nodes of the graph by one. All other edges connecting either or are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probabil
known for
known for
seeAlso
primaryTopic
Karger's algorithm
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 . Informally speaking, the contraction of an edge merges the nodes and into one, reducing the total number of nodes of the graph by one. All other edges connecting either or are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probabil
has abstract
En algorithmique des graphes, ...... ons ont ensuite été proposées.
@fr
In computer science and graph ...... e found with high probability.
@en
Алгори́тм Ка́ргера (англ. Karg ...... ыть найден минимальный разрез.
@ru
Wikipage page ID
11,491,940
page length (characters) of wiki page
Wikipage revision ID
1,018,565,086
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
comment
En algorithmique des graphes, ...... écroître le nombre de sommets.
@fr
In computer science and graph ...... an be found with high probabil
@en
Алгори́тм Ка́ргера (англ. Karg ...... ром и опубликован в 1993 году.
@ru
label
Algorithme de Karger
@fr
Karger's algorithm
@en
Алгоритм Каргера
@ru