| dbo:abstract
|
- 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 probability. (en)
- En algorithmique des graphes, l'algorithme de Karger est un algorithme probabiliste pour le problème de la coupe minimum (MIN-CUT). C'est donc un algorithme utilisant une source d'aléas, pour produire une solution correcte avec une bonne probabilité. Le problème en question est le suivant : étant donné un graphe non orienté trouver un ensemble de sommets non trivial minimisant le nombre d'arêtes sortant de cet ensemble. L'outil principal de l'algorithme est la contraction aléatoire d'arêtes, qui fait décroître le nombre de sommets. Il est dû à David Karger et a été publié en 1993. Plusieurs variations ont ensuite été proposées. (fr)
- Алгори́тм Ка́ргера (англ. Karger's algorithm) — в информатике и теории графов является вероятностным алгоритмом, позволяющим найти минимальный разрез связного графа. Алгоритм изобретен Девидом Каргером и опубликован в 1993 году. Идея алгоритма основана на стягивании ребра в неориентированном графе. Во время стягивания ребра происходит объединение двух вершин в одну, что уменьшает количество вершин графа на единицу. Все рёбра стягиваемых вершин соединяются со вновь образованной вершиной, порождая мультиграф. Алгоритм Каргера итеративно выбирает случайные рёбра и выполняет операцию до тех пор, пока не останется две вершины, которые и представляют собой разрез изначального графа. Если повторять алгоритм достаточное количество раз, то с высокой вероятностью может быть найден минимальный разрез. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13471 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 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 (en)
- En algorithmique des graphes, l'algorithme de Karger est un algorithme probabiliste pour le problème de la coupe minimum (MIN-CUT). C'est donc un algorithme utilisant une source d'aléas, pour produire une solution correcte avec une bonne probabilité. Le problème en question est le suivant : étant donné un graphe non orienté trouver un ensemble de sommets non trivial minimisant le nombre d'arêtes sortant de cet ensemble. L'outil principal de l'algorithme est la contraction aléatoire d'arêtes, qui fait décroître le nombre de sommets. (fr)
- Алгори́тм Ка́ргера (англ. Karger's algorithm) — в информатике и теории графов является вероятностным алгоритмом, позволяющим найти минимальный разрез связного графа. Алгоритм изобретен Девидом Каргером и опубликован в 1993 году. (ru)
|
| rdfs:label
|
- Algorithme de Karger (fr)
- Karger's algorithm (en)
- Алгоритм Каргера (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
