In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - خوارزمية هوبكروفت-كارب (ar)
- Algorithmus von Hopcroft und Karp (de)
- Algorithme de Hopcroft-Karp (fr)
- Hopcroft–Karp algorithm (en)
- Algoritmo de Hopcroft–Karp (pt)
- Алгоритм Хопкрофта — Карпа (ru)
- 霍普克洛夫特－卡普算法 (zh)
- Алгоритм Гопкрофта — Карпа (uk)
|
| rdfs:comment
| - هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت و كارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات). (ar)
- Der Algorithmus von Hopcroft und Karp (1973 von John E. Hopcroft und Richard M. Karp entwickelt) dient in der Graphentheorie zur Bestimmung eines Matchings mit maximaler Kardinalität in einem bipartiten Graphen. Er geht aus von dem Matching, die keine Kanten enthält, und konstruiert dazu alternierende Pfade zwischen noch ungepaarten Knoten. Jeder solche Pfad liefert eine Vergrößerung (Augmentierung) des Matchings um eine Kante. (de)
- In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability. (en)
- 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)
- Em ciência da computação, o algoritmo de Hopcroft–Karp é um algoritmo que recebe como entrada um grafo bipartido e produz como saída um máximo de cardinalidade de acoplamento – um conjunto de quantas arestas forem possíveis com a propriedade de que não há duas bordas compartilhando um ponto na extremidade. Ele roda em tempo no pior caso, onde é o conjunto de arestas do grafo, e é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se e para grafos aleatórios ele é executado em tempo quase linear. (pt)
- Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет в худшем случае (здесь — множество рёбер графа, а — множество его вершин). В случае плотных графов время работы ограничивается , а для случайного графа алгоритм работает почти за линейное время. (ru)
- 霍普克洛夫特－卡普算法（Hopcroft Karp算法）是用來解決二分圖最大匹配問題的一種演算法。 在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是，一共需要增广次，因此总时间复杂度为。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样迭代次数最多为，所以，时间复杂度就降到了。 该算法由John E.Hopcroft和Richard M.Karp于1973年提出，故称霍普克洛夫特－卡普算法。 (zh)
- В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час у найгіршому випадку, де це множина ребер і це множина вершин графа. У випадку часові рамки набувають вигляду , для випадкових графів час виконання майже лінійний. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| authorlink
| - Alexander V. Karzanov (en)
|
| class
| |
| data
| |
| first
| - John (en)
- Alexander (en)
- Richard (en)
|
| last
| - Karp (en)
- Hopcroft (en)
- Karzanov (en)
|
| year
| |
| has abstract
| - هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت و كارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات). (ar)
- Der Algorithmus von Hopcroft und Karp (1973 von John E. Hopcroft und Richard M. Karp entwickelt) dient in der Graphentheorie zur Bestimmung eines Matchings mit maximaler Kardinalität in einem bipartiten Graphen. Er geht aus von dem Matching, die keine Kanten enthält, und konstruiert dazu alternierende Pfade zwischen noch ungepaarten Knoten. Jeder solche Pfad liefert eine Vergrößerung (Augmentierung) des Matchings um eine Kante. (de)
- In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability. The algorithm was discovered by John Hopcroft and Richard Karp and independently by Alexander Karzanov. As in previous methods for matching such as the Hungarian algorithm and the work of , the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the Ford–Fulkerson algorithm‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only iterations are needed instead of iterations. The same performance of can be achieved to find maximum cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani. The Hopcroft–Karp algorithm can be seen as a special case of Dinic's algorithm for the maximum flow problem. (en)
- 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
