| Property |
Value |
| dbo:abstract
|
- En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). L'algorithme a été décrit par John Hopcroft et Richard Karp en 1973. De même nature que d'autres algorithmes antérieurs de calcul de couplages comme l'algorithme hongrois ou la méthode d'Edmonds, l'algorithme de Hopcroft-Karp incrémente itérativement la taille d'un couplage partiel par le calcul de chemins d'augmentation : ce sont des suites d'arêtes qui sont alternativement dans et en dehors du couplage, de sorte que le remplacement des arêtes dans le couplage par celles qui sont en dehors produit un couplage plus grand. Toutefois, au lieu de déterminer juste un seul chemin d'augmentation à chaque itération, l'algorithme calcule à chaque phase un ensemble maximal de chemins d'augmentation de longueur minimale. Il en résulte que itérations suffisent. Le même principe a aussi été employé pour développer des algorithmes plus compliqués de couplage dans des graphes non bipartis, avec la même complexité en temps que l’algorithme de Hopcroft-Karp. (fr)
- En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). L'algorithme a été décrit par John Hopcroft et Richard Karp en 1973. De même nature que d'autres algorithmes antérieurs de calcul de couplages comme l'algorithme hongrois ou la méthode d'Edmonds, l'algorithme de Hopcroft-Karp incrémente itérativement la taille d'un couplage partiel par le calcul de chemins d'augmentation : ce sont des suites d'arêtes qui sont alternativement dans et en dehors du couplage, de sorte que le remplacement des arêtes dans le couplage par celles qui sont en dehors produit un couplage plus grand. Toutefois, au lieu de déterminer juste un seul chemin d'augmentation à chaque itération, l'algorithme calcule à chaque phase un ensemble maximal de chemins d'augmentation de longueur minimale. Il en résulte que itérations suffisent. Le même principe a aussi été employé pour développer des algorithmes plus compliqués de couplage dans des graphes non bipartis, avec la même complexité en temps que l’algorithme de Hopcroft-Karp. (fr)
|
| dbo:basedOn
| |
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 24859 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1965 (xsd:integer)
- 1973 (xsd:integer)
- 1980 (xsd:integer)
- 1988 (xsd:integer)
- 1991 (xsd:integer)
- 1993 (xsd:integer)
- 1994 (xsd:integer)
- 1996 (xsd:integer)
- 2001 (xsd:integer)
- 2006 (xsd:integer)
- 2010 (xsd:integer)
- 2012 (xsd:integer)
|
| prop-fr:arxiv
| |
| prop-fr:auteur
| |
| prop-fr:consultéLe
| |
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.110900 (xsd:double)
- 10.113700 (xsd:double)
- 10.114500 (xsd:double)
- 10.415300 (xsd:double)
|
| prop-fr:jour
| |
| prop-fr:journal
|
- dbpedia-fr:Algorithmica
- Canadian J. Math (fr)
- CoRR abs/1210.4594 (fr)
- Information Processing Letters (fr)
- Journal of the ACM (fr)
- SIAM Journal on Computing (fr)
- Theory of Computing Systems (fr)
- Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas (fr)
- Symposium on Foundations of Computer Science-Proc. 21st IEEE Symp. Foundations of Computer Science (fr)
- Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn (fr)
|
| prop-fr:libellé
|
- 1991 (xsd:integer)
- 1993 (xsd:integer)
- 2006 (xsd:integer)
|
| prop-fr:lienAuteur
|
- John Hopcroft (fr)
- Jack Edmonds (fr)
- Kurt Mehlhorn (fr)
- Richard Karp (fr)
- Robert Tarjan (fr)
- John Hopcroft (fr)
- Jack Edmonds (fr)
- Kurt Mehlhorn (fr)
- Richard Karp (fr)
- Robert Tarjan (fr)
|
| prop-fr:mathReviews
| |
| prop-fr:mois
|
- janvier (fr)
- janvier (fr)
|
| prop-fr:nom
|
- Paul (fr)
- Peterson (fr)
- Edmonds (fr)
- Schafer (fr)
- Hopcroft (fr)
- Alt (fr)
- Bast (fr)
- Blum (fr)
- Karp (fr)
- Loui (fr)
- Mehlhorn (fr)
- Setubal (fr)
- Tamaki (fr)
- Tarjan (fr)
- Vazirani (fr)
- Paul (fr)
- Peterson (fr)
- Edmonds (fr)
- Schafer (fr)
- Hopcroft (fr)
- Alt (fr)
- Bast (fr)
- Blum (fr)
- Karp (fr)
- Loui (fr)
- Mehlhorn (fr)
- Setubal (fr)
- Tamaki (fr)
- Tarjan (fr)
- Vazirani (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 4 (xsd:integer)
- 6 (xsd:integer)
|
| prop-fr:pages
|
- 3 (xsd:integer)
- 17 (xsd:integer)
- 225 (xsd:integer)
- 237 (xsd:integer)
- 449 (xsd:integer)
- 511 (xsd:integer)
- 815 (xsd:integer)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- Holger (fr)
- Manfred (fr)
- Kurt (fr)
- Richard M. (fr)
- Helmut (fr)
- John E. (fr)
- Norbert (fr)
- Guido (fr)
- Jack (fr)
- Robert E. (fr)
- Paul A. (fr)
- Hisao (fr)
- João C. (fr)
- Michael C. (fr)
- Vijay (fr)
- Holger (fr)
- Manfred (fr)
- Kurt (fr)
- Richard M. (fr)
- Helmut (fr)
- John E. (fr)
- Norbert (fr)
- Guido (fr)
- Jack (fr)
- Robert E. (fr)
- Paul A. (fr)
- Hisao (fr)
- João C. (fr)
- Michael C. (fr)
- Vijay (fr)
|
| prop-fr:périodique
| |
| prop-fr:titre
|
- An n5/2 algorithm for maximum matchings in bipartite graphs (fr)
- Average-case analysis of algorithms for matchings and related problems (fr)
- Faster scaling algorithms for general graph matching problems (fr)
- Sequential and parallel experimental results with bipartite matching algorithms (fr)
- Matchings in Graphs (fr)
- Network Flows: Theory, Algorithms and Applications (fr)
- Paths, Trees and Flowers (fr)
- An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm (fr)
- A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs (fr)
- The general maximum matching algorithm of Micali and Vazirani (fr)
- Matching algorithms are fast in sparse random graphs (fr)
- An algorithm for finding maximum matching in general graphs (fr)
- Computing a maximum cardinality matching in a bipartite graph in time (fr)
- An n5/2 algorithm for maximum matchings in bipartite graphs (fr)
- Average-case analysis of algorithms for matchings and related problems (fr)
- Faster scaling algorithms for general graph matching problems (fr)
- Sequential and parallel experimental results with bipartite matching algorithms (fr)
- Matchings in Graphs (fr)
- Network Flows: Theory, Algorithms and Applications (fr)
- Paths, Trees and Flowers (fr)
- An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm (fr)
- A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs (fr)
- The general maximum matching algorithm of Micali and Vazirani (fr)
- Matching algorithms are fast in sparse random graphs (fr)
- An algorithm for finding maximum matching in general graphs (fr)
- Computing a maximum cardinality matching in a bipartite graph in time (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 2 (xsd:integer)
- 3 (xsd:integer)
- 17 (xsd:integer)
- 37 (xsd:integer)
- 38 (xsd:integer)
- 39 (xsd:integer)
- 41 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Prentice-Hall (fr)
- The Institute of Mathematical Sciences (fr)
- Prentice-Hall (fr)
- The Institute of Mathematical Sciences (fr)
|
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). (fr)
- En informatique, l'algorithme de Hopcroft-Karp est un algorithme qui prend en entrée un graphe biparti et qui produit en sortie un couplage de cardinalité maximum, c'est-à-dire un ensemble d'arêtes aussi grand que possible avec la propriété que deux arêtes ne partagent jamais une extrémité. L'algorithme a une complexité en temps en dans le pire des cas, où est l'ensemble des arêtes et est l'ensemble des sommets du graphe, et il est supposé que . Dans le cas de graphes denses, la borne devient , et pour des graphes aléatoires creux, le temps est pratiquement linéaire (en ). (fr)
|
| rdfs:label
|
- Algorithme de Hopcroft-Karp (fr)
- Hopcroft–Karp algorithm (en)
- Алгоритм Гопкрофта — Карпа (uk)
- Алгоритм Хопкрофта — Карпа (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
