| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11107 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1993 (xsd:integer)
- 1996 (xsd:integer)
|
| prop-fr:auteur
| |
| prop-fr:date
|
- 2010 (xsd:integer)
- 2012 (xsd:integer)
- 2013 (xsd:integer)
|
| prop-fr:doi
| |
| prop-fr:langue
| |
| prop-fr:lienPériodique
|
- Journal of the ACM (fr)
- Journal of the ACM (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Stein (fr)
- Karger (fr)
- Stein (fr)
- Karger (fr)
|
| prop-fr:numéro
| |
| prop-fr:numéroChapitre
| |
| prop-fr:passage
|
- 7 (xsd:integer)
- 601 (xsd:integer)
- 757 (xsd:integer)
|
| prop-fr:prénom
|
- David (fr)
- David R. (fr)
- Clifford (fr)
- David (fr)
- David R. (fr)
- Clifford (fr)
|
| prop-fr:périodique
|
- Journal of the ACM (fr)
- Journal of the ACM (fr)
|
| prop-fr:site
| |
| prop-fr:titre
|
- A new approach to the minimum cut problem (fr)
- A new approach to the minimum cut problem (fr)
|
| prop-fr:titreChapitre
|
- Introduction (fr)
- An algorithm for minimum cuts (fr)
- Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm (fr)
- Introduction (fr)
- An algorithm for minimum cuts (fr)
- Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm (fr)
|
| prop-fr:titreOuvrage
|
- STOC (fr)
- Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (fr)
- STOC (fr)
- Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (fr)
|
| prop-fr:url
|
- https://www.ceid.upatras.gr/webpages/courses/pithmeth/slides/lecture1.pdf|titre=The Probabilistic Method - Randomized Algorithms : A Monte Carlo Minimum Cut Algorithm (fr)
- https://www.dailymotion.com/video/xuxog2_mpri-2012-algorithmes-randomises-2a_tech|titre= Description de l'algorithme en vidéo (fr)
- http://www.cc.gatech.edu/~vigoda/7530-Spring10/Kargers-MinCut.pdf|langue=en|titre= Notes de cours sur l'algorithme de Karger (fr)
- http://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec2final.pdf|titre= Notes de cours (fr)
- https://www.ceid.upatras.gr/webpages/courses/pithmeth/slides/lecture1.pdf|titre=The Probabilistic Method - Randomized Algorithms : A Monte Carlo Minimum Cut Algorithm (fr)
- https://www.dailymotion.com/video/xuxog2_mpri-2012-algorithmes-randomises-2a_tech|titre= Description de l'algorithme en vidéo (fr)
- http://www.cc.gatech.edu/~vigoda/7530-Spring10/Kargers-MinCut.pdf|langue=en|titre= Notes de cours sur l'algorithme de Karger (fr)
- http://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec2final.pdf|titre= Notes de cours (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Algorithme de Karger (fr)
- Karger's algorithm (en)
- Thuật toán Karger (vi)
- Алгоритм Каргера (ru)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |