| http://dbpedia.org/ontology/abstract
|
L'algorithme de Dinic ou algorithme de Din … L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.met d'obtenir cette meilleure performance.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_G1.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf +
, http://www.cs.bgu.ac.il/~dinitz/D70.pdf +
|
| http://dbpedia.org/ontology/wikiPageID
|
7818425
|
| http://dbpedia.org/ontology/wikiPageLength
|
12104
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
168243483
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_G2.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_G3.svg +
, http://fr.dbpedia.org/resource/Algorithme_d%27Edmonds-Karp +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_G1.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_GL3.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_Gf1.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_GL1.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_GL2.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_Gf2.svg +
, http://fr.dbpedia.org/resource/Fichier:Dinic_algorithm_Gf3.svg +
, http://fr.dbpedia.org/resource/Couplage_%28th%C3%A9orie_des_graphes%29 +
, http://fr.dbpedia.org/resource/Complexit%C3%A9_en_temps +
, http://fr.dbpedia.org/resource/Rideau_de_fer +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_de_flot_maximum +
, http://fr.dbpedia.org/resource/Universit%C3%A9_Ben_Gourion_du_N%C3%A9guev +
, http://fr.dbpedia.org/resource/Algorithme_de_Ford-Fulkerson +
, http://fr.dbpedia.org/resource/Algorithme_de_Hopcroft-Karp +
, http://fr.dbpedia.org/resource/Algorithme_de_parcours_en_largeur +
, http://fr.dbpedia.org/resource/Robert_Tarjan +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:R%C3%A9seau_de_flot +
, http://fr.dbpedia.org/resource/Shimon_Even +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Algorithme_de_la_th%C3%A9orie_des_graphes +
|
| http://fr.dbpedia.org/property/année
|
2010
, 2008
, 2006
, 2001
, 1983
, 1970
|
| http://fr.dbpedia.org/property/auteur
|
Jean Fonlupt et Alexandre Skoda
|
| http://fr.dbpedia.org/property/auteursOuvrage
|
Oded Goldreich, Arnold L. Rosenberg et Alan L. Selman
|
| http://fr.dbpedia.org/property/collection
|
IRIS
, Algorithms and Combinatorics
|
| http://fr.dbpedia.org/property/fr
|
link/cut tree
|
| http://fr.dbpedia.org/property/isbn
|
978
|
| http://fr.dbpedia.org/property/journal
|
Soviet Math. Doklady
|
| http://fr.dbpedia.org/property/langue
|
en
, fr
|
| http://fr.dbpedia.org/property/lccn
|
2001031277
|
| http://fr.dbpedia.org/property/lieu
|
Cambridge
|
| http://fr.dbpedia.org/property/nom
|
Stein
, Vygen
, Cormen
, Tarjan
, Dinic
, Rivest
, Dinitz
, Korte
, Leiserson
|
| http://fr.dbpedia.org/property/numéroChapitre
|
26
|
| http://fr.dbpedia.org/property/numéroD'édition
|
2
|
| http://fr.dbpedia.org/property/numéroDansCollection
|
21
|
| http://fr.dbpedia.org/property/pages
|
1277
|
| http://fr.dbpedia.org/property/pagesTotales
|
627
, 1180
|
| http://fr.dbpedia.org/property/passage
|
643
, 174
, 180
, 218
|
| http://fr.dbpedia.org/property/prénom
|
Bernard H.
, Charles E.
, Jens
, Robert E.
, Thomas H.
, Bernard
, Clifford
, Ronald L.
, Yefim
, E. A.
|
| http://fr.dbpedia.org/property/responsabilité
|
traducteurs
|
| http://fr.dbpedia.org/property/sousTitre
|
Theory and Algorithms
, théorie et algorithmes
|
| http://fr.dbpedia.org/property/texte
|
link/cut tree
|
| http://fr.dbpedia.org/property/titre
|
Algorithm for solution of a problem of maximum flow in a network with power estimation
, Optimisation combinatoire
, Combinatorial Optimization
, Data structures and network algorithms
, Introduction to Algorithms
|
| http://fr.dbpedia.org/property/titreChapitre
|
Dinitz' Algorithm: The Original Version and Even's Version
, 8.4
, Chap. 26 Flows
|
| http://fr.dbpedia.org/property/titreOuvrage
|
Theoretical Computer Science: Essays in Memory of Shimon Even
|
| http://fr.dbpedia.org/property/trad
|
link/cut tree
|
| http://fr.dbpedia.org/property/url
|
http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf +
, http://www.cs.bgu.ac.il/~dinitz/D70.pdf +
|
| http://fr.dbpedia.org/property/volume
|
11
|
| http://fr.dbpedia.org/property/wikiPageUsesTemplate
|
http://fr.dbpedia.org/resource/Mod%C3%A8le:Chapitre +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Lien +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Portail +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Article +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:R%C3%A9f%C3%A9rences +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Sfn +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:2e +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Ouvrage +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:%27 +
|
| http://fr.dbpedia.org/property/éditeur
|
MIT Press and McGraw-Hill
, Springer
, Springer-France
, Doklady Nauk SSSR
|
| http://purl.org/dc/terms/subject
|
http://fr.dbpedia.org/resource/Cat%C3%A9gorie:R%C3%A9seau_de_flot +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Algorithme_de_la_th%C3%A9orie_des_graphes +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://fr.wikipedia.org/wiki/Algorithme_de_Dinic?oldid=168243483&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_GL3.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_Gf1.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_Gf2.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_Gf3.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_G2.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_G3.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_GL1.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_GL2.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Dinic_algorithm_G1.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://fr.wikipedia.org/wiki/Algorithme_de_Dinic +
|
| owl:sameAs |
http://es.dbpedia.org/resource/Algoritmo_de_Dinic +
, http://uk.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D1%96%D0%BD%D1%96%D1%86%D0%B0 +
, http://pl.dbpedia.org/resource/Algorytm_Dynica +
, http://fa.dbpedia.org/resource/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%D9%86%DB%8C%DA%A9 +
, http://de.dbpedia.org/resource/Algorithmus_von_Dinic +
, http://cs.dbpedia.org/resource/Dinic%C5%AFv_algoritmus +
, http://www.wikidata.org/entity/Q730933 +
, http://dbpedia.org/resource/Dinic%27s_algorithm +
, http://g.co/kg/m/06zpk1k +
, http://ru.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 +
, http://fr.dbpedia.org/resource/Algorithme_de_Dinic +
, http://zh.dbpedia.org/resource/%E8%BF%AA%E5%B0%BC%E8%8C%A8%E7%AE%97%E6%B3%95 +
, http://ma-graph.org/entity/109111794 +
, http://vi.dbpedia.org/resource/Thu%E1%BA%ADt_to%C3%A1n_Dinitz +
, http://sr.dbpedia.org/resource/%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%BE%D0%B2_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%B0%D0%BC +
, http://th.dbpedia.org/resource/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B8%82%E0%B8%AD%E0%B8%87%E0%B8%94%E0%B8%B5%E0%B8%99%E0%B8%B4%E0%B8%8B +
|
| rdf:type |
http://www.wikidata.org/entity/Q8366 +
, http://dbpedia.org/ontology/Algorithm +
|
| rdfs:comment |
L'algorithme de Dinic ou algorithme de Din … L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance.met d'obtenir cette meilleure performance.
|
| rdfs:label |
Thuật toán Dinitz
, Алгоритм Диница
, Dinic's algorithm
, Algorithme de Dinic
, Алгоритм Дініца
|
