Karger's algorithm (original) (raw)
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
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Min_cut_example.svg?width=300 |
| dbo:wikiPageID | 11491940 (xsd:integer) |
| dbo:wikiPageLength | 13471 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1085606025 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Push–relabel_maximum_flow_algorithm dbr:Multigraph dbr:David_Karger dbr:Dense_graph dbc:Graph_connectivity dbr:Degree_(graph_theory) dbr:Max-flow_min-cut_theorem dbr:Clifford_Stein dbr:Graph_(discrete_mathematics) dbr:Computer_science dbc:Graph_algorithms dbr:Minimum_cut dbr:Adjacency_list dbr:Adjacency_matrix dbr:Cut_(graph_theory) dbr:Cycle_graph dbr:Graph_theory dbr:Edge_contraction dbr:Polynomial_time dbr:Maximum_flow dbr:Minimum_spanning_tree dbr:Randomized_algorithm dbr:With_high_probability dbr:Stoer–Wagner_algorithm dbr:Kruskal’s_algorithm dbr:File:10_repetitions_of_Karger’s_contraction_procedure.svg dbr:File:Edge_contraction_in_a_multigraph.svg dbr:File:Min_cut_example.svg dbr:File:Single_run_of_Karger’s_Mincut_algorithm.svg dbr:File:Spanning_tree_interpretation_of_Karger’s_algorithm.svg |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:Short_description |
| dct:subject | dbc:Graph_connectivity dbc:Graph_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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 | freebase:Karger's algorithm yago-res:Karger's algorithm wikidata:Karger's algorithm dbpedia-fa:Karger's algorithm dbpedia-fr:Karger's algorithm dbpedia-ru:Karger's algorithm dbpedia-sr:Karger's algorithm dbpedia-th:Karger's algorithm dbpedia-vi:Karger's algorithm https://global.dbpedia.org/id/4ZJpe |
| prov:wasDerivedFrom | wikipedia-en:Karger's_algorithm?oldid=1085606025&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Single_run_of_Karger’s_Mincut_algorithm.svg wiki-commons:Special:FilePath/10_repetitions_of_Karger’s_contraction_procedure.svg wiki-commons:Special:FilePath/Edge_contraction_in_a_multigraph.svg wiki-commons:Special:FilePath/Spanning_tree_interpretation_of_Karger’s_algorithm.svg wiki-commons:Special:FilePath/Min_cut_example.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Karger's_algorithm |
| is dbo:knownFor of | dbr:David_Karger |
| is dbo:wikiPageRedirects of | dbr:Karger's_Randomize_Min-Cut_Algorithm dbr:Karger's_randomize_min-cut_algorithm dbr:Karger’s_algorithm dbr:Random_contraction_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Monte_Carlo_algorithm dbr:David_Karger dbr:Timeline_of_algorithms dbr:K-edge-connected_graph dbr:Minimum_cut dbr:Randomized_algorithm dbr:Karger's_Randomize_Min-Cut_Algorithm dbr:Karger's_randomize_min-cut_algorithm dbr:Karger’s_algorithm dbr:Random_contraction_algorithm |
| is dbp:knownFor of | dbr:David_Karger |
| is rdfs:seeAlso of | dbr:HCS_clustering_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Karger's_algorithm |
