About: Hopcroft–Karp algorithm

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Hopcroft–Karp algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : wikidata:Q8366, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

Attributes	Values
rdf:type	Thing Algorithm Algorithm
rdfs:label	Algorithme de Hopcroft-Karp (fr) Hopcroft–Karp algorithm (en) Алгоритм Гопкрофта — Карпа (uk) Алгоритм Хопкрофта — Карпа (ru)
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)
sameAs	Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm Hopcroft–Karp algorithm
Wikipage page ID	11589817 (xsd:integer)
Wikipage revision ID	185492029 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Couplage_(théorie_des_graphes) Algorithm Edmonds–Karp algorithm Dinic's algorithm Breadth-first search Depth-first search Push–relabel maximum flow algorithm Hungarian algorithm Algorithmica Algebra of sets dbpedia-fr:Cardinalité_(mathématiques) category-fr:Algorithme_de_la_théorie_des_graphes Average-case complexity Time complexity dbpedia-fr:Couplage_(théorie_des_graphes) dbpedia-fr:Densité_d'un_graphe dbpedia-fr:Graphe_aléatoire dbpedia-fr:Graphe_biparti dbpedia-fr:Harold_Gabow Computer science dbpedia-fr:John_Hopcroft Journal of the ACM dbpedia-fr:Logarithme dbpedia-fr:Problème_d'affectation dbpedia-fr:Problème_de_flot_maximum Pseudocode Rajeev Motwani Richard M. Karp dbpedia-fr:Réseau_de_flot
Link from a Wikipage to an external page	http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85232-CS.ps.gz http://www.imsc.res.in/~meena/matching/hopcroft-karp.pdf https://brilliant.org/wiki/hopcroft-karp/ https://www-m9.ma.tum.de/graph-algorithms/matchings-hopcroft-karp/index_en.html http://citeseerx.ist.psu.edu/viewdoc/summary%3Fdoi=10.1.1.48.3539
page length (characters) of wiki page	24859 (xsd:nonNegativeInteger)
dct:subject	category-fr:Couplage_(théorie_des_graphes) category-fr:Algorithme_de_la_théorie_des_graphes
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:' dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Harvsp dbpedia-fr:Modèle:Lien_web dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Infobox_Algorithme2
prov:wasDerivedFrom	wikipedia-fr:Algorithme_de_Hopcroft-Karp?oldid=185492029&ns=0
foaf:depiction
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	1210 (xsd:double)
prop-fr:auteur	dbpedia-fr:Harold_Gabow Rajeev Motwani James B. Orlin (fr) Meena Mahajan (fr) Ravindra K. Ahuja (fr) Silvio Micali (fr) Thomas L. Magnanti (fr) Vijay Vazirani (fr)
prop-fr:consultéLe	2018-03-27 (xsd:date)
prop-fr:doi	10 (xsd:double) 10 (xsd:double) 10 (xsd:double) 10 (xsd:double)

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 14 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software