Hopcroft–Karp algorithm
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.
known for
3-dimensional matchingAlexander V. KarzanovBipartite graphDinic's algorithmGraph theoryHall violatorHopcroft-KarpHopcroft-Karp-Karzanov algorithmHopcroft-Karp algorithmHopcroft KarpHopcroft–Karp–Karzanov algorithmJohn HopcroftKőnig's theorem (graph theory)List of algorithmsMatching (graph theory)Maximum cardinality matchingNetwork controllabilityRichard M. KarpSyntactic pattern recognitionTimeline of algorithms♯P-completeness of 01-permanent
Link from a Wikipage to another Wikipage
known for
primaryTopic
Hopcroft–Karp algorithm
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.
has abstract
Em ciência da computação, o al ...... do algoritmo de Hopcroft–Karp.
@pt
En informatique, l'algorithme ...... l’algorithme de Hopcroft-Karp.
@fr
Алгоритм Хопкрофта — Карпа — а ...... у алгоритма Хопкрофта — Карпа.
@ru
В інформатиці, алгоритм Гопкро ...... к у алгоритму Гопкрофта—Карпа.
@uk
هذه الخوارزمية تبحث عن الاقترا ...... روبوتات (أو أ سراب الروبوتات).
@ar
霍普克洛夫特-卡普算法(Hopcroft Karp算法)是用 ...... n inc(ans); writeln(ans); end.
@zh
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,020,785,010
Link from a Wikipage to another Wikipage
author1-link
John Hopcroft
@en
author2-link
Richard Karp
@en
authorlink
Alexander V. Karzanov
@en
class
Graph algorithm
@en
first
Alexander
@en
John
@en
Richard
@en
last
Hopcroft
@en
Karp
@en
Karzanov
@en
wikiPageUsesTemplate
comment
Em ciência da computação, o al ...... ecutado em tempo quase linear.
@pt
En informatique, l'algorithme ...... t pratiquement linéaire (en ).
@fr
Алгоритм Хопкрофта — Карпа — а ...... отает почти за линейное время.
@ru
В інформатиці, алгоритм Гопкро ...... час виконання майже лінійний.
@uk
هذه الخوارزمية تبحث عن الاقترا ...... روبوتات (أو أ سراب الروبوتات).
@ar
霍普克洛夫特-卡普算法(Hopcroft Karp算法)是用 ...... M.Karp于1973年提出,故称霍普克洛夫特-卡普算法。
@zh
label
Algorithme de Hopcroft-Karp
@fr
Algorithmus von Hopcroft und Karp
@de
Algoritmo de Hopcroft–Karp
@pt
Hopcroft–Karp algorithm
@en
Алгоритм Гопкрофта — Карпа
@uk
Алгоритм Хопкрофта — Карпа
@ru
خوارزمية هوبكروفت-كارب
@ar
霍普克洛夫特-卡普算法
@zh