Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Hopcroft–Karp_algorithm> ?p ?o. }
Showing items 1 to 21 of
21
with 100 items per page.
- Hopcroft–Karp_algorithm abstract "In computer science, the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – 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, and is set of vertices of the graph. In the case of dense graphs the time bound becomes , and for random graphs it runs in near-linear time.The algorithm was found by John Hopcroft and Richard Karp (1973). As in previous methods for matching such as the Hungarian algorithm and the work of Edmonds (1965), the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths. As a result only iterations are needed. The same principle has also been used to develop more complicated algorithms for non-bipartite matching with the same asymptotic running time as the Hopcroft–Karp algorithm.".
- Hopcroft–Karp_algorithm wikiPageID "5944391".
- Hopcroft–Karp_algorithm wikiPageRevisionID "593898016".
- Hopcroft–Karp_algorithm author1Link "John Hopcroft".
- Hopcroft–Karp_algorithm author2Link "Richard Karp".
- Hopcroft–Karp_algorithm first "John".
- Hopcroft–Karp_algorithm first "Richard".
- Hopcroft–Karp_algorithm last "Hopcroft".
- Hopcroft–Karp_algorithm last "Karp".
- Hopcroft–Karp_algorithm year "1973".
- Hopcroft–Karp_algorithm subject Category:Graph_algorithms.
- Hopcroft–Karp_algorithm subject Category:Matching.
- Hopcroft–Karp_algorithm comment "In computer science, the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – 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, and is set of vertices of the graph.".
- Hopcroft–Karp_algorithm label "Algorithmus von Hopcroft und Karp".
- Hopcroft–Karp_algorithm label "Hopcroft–Karp algorithm".
- Hopcroft–Karp_algorithm label "霍普克洛夫特-卡普算法".
- Hopcroft–Karp_algorithm sameAs Hopcroft%E2%80%93Karp_algorithm.
- Hopcroft–Karp_algorithm sameAs Algorithmus_von_Hopcroft_und_Karp.
- Hopcroft–Karp_algorithm sameAs Q1516988.
- Hopcroft–Karp_algorithm sameAs Q1516988.
- Hopcroft–Karp_algorithm wasDerivedFrom Hopcroft–Karp_algorithm?oldid=593898016.