This HTML5 document contains 78 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n22http://commons.dbpedia.org/resource/Category:
n16http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-plhttp://pl.dbpedia.org/resource/
n17http://fr.dbpedia.org/resource/Modèle:
n15https://pacechallenge.org/2019/vc/
n18http://fr.dbpedia.org/resource/Fichier:
n12http://commons.wikimedia.org/wiki/Special:FilePath/
wikipedia-frhttp://fr.wikipedia.org/wiki/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://www.nada.kth.se/~viggo/wwwcompendium/
owlhttp://www.w3.org/2002/07/owl#
n31https://commons.wikimedia.org/wiki/Category:
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-idhttp://id.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Problème_de_couverture_par_sommets
rdfs:label
Knotenüberdeckungsproblem Problème de couverture par sommets Задача о вершинном покрытии Problema di copertura dei vertici 覆盖 (图论)
rdfs:comment
En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, Vertex Cover en anglais) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes. Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.
rdfs:seeAlso
n31:Vertex_cover_problem
owl:sameAs
dbpedia-ja:頂点被覆 dbpedia-it:Problema_di_copertura_dei_vertici wikidata:Q924362 n16:022rkw dbpedia-sr:Покривач_чворова dbpedia-tr:Kenar_kapsama_problemi n22:Vertex_cover_problem dbpedia-id:Tutup_verteks dbpedia-de:Knotenüberdeckungsproblem dbpedia-he:בעיית_כיסוי_קודקודים dbpedia-fa:پوشش_گره‌ای dbpedia-pl:Problem_pokrycia_wierzchołkowego dbpedia-zh:覆盖_(图论) dbpedia-ru:Задача_о_вершинном_покрытии
dbo:wikiPageID
2894443
dbo:wikiPageRevisionID
181353404
dbo:wikiPageWikiLink
dbpedia-fr:Graphe_cubique dbpedia-fr:Problème_du_stable_maximum dbpedia-fr:Théorème_de_Kőnig_(théorie_des_graphes) dbpedia-fr:Optimisation_linéaire_en_nombres_entiers dbpedia-fr:Couplage_(théorie_des_graphes) dbpedia-fr:Conjecture_des_jeux_uniques dbpedia-fr:Problème_de_décision dbpedia-fr:Degré_(théorie_des_graphes) dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Problème_NP-complet dbpedia-fr:Graphe_planaire n18:Vertex-cover.svg dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) n18:Couverture_de_sommets.svg category-fr:Problème_NP-complet dbpedia-fr:21_problèmes_NP-complets_de_Karp dbpedia-fr:Stable_(théorie_des_graphes) n18:Minimum-vertex-cover.svg dbpedia-fr:Algorithme_d'approximation dbpedia-fr:Tibor_Gallai dbpedia-fr:Théorie_des_graphes dbpedia-fr:Optimisation_(mathématiques) dbpedia-fr:Clique_(théorie_des_graphes) category-fr:Théorie_des_graphes dbpedia-fr:Informatique_théorique dbpedia-fr:Complexité_paramétrée
dbo:wikiPageExternalLink
n15: n10:node10.html
dbo:wikiPageLength
7612
dct:subject
category-fr:Théorie_des_graphes category-fr:Problème_NP-complet
prop-fr:wikiPageUsesTemplate
n17:Théorème n17:Palette_21_problèmes_NP-complets_de_Karp n17:Lien_web n17:Portail n17:Langue
prov:wasDerivedFrom
wikipedia-fr:Problème_de_couverture_par_sommets?oldid=181353404&ns=0
foaf:depiction
n12:Vertex-cover.svg n12:Minimum-vertex-cover.svg n12:Couverture_de_sommets.svg
prop-fr:auteur
Viggo Kann
prop-fr:consultéLe
2014-08-06
prop-fr:date
2000-03-20 2019
prop-fr:langue
en
prop-fr:site
A compendium of NP optimization problems Parameterized Algorithms and Computational Experiments Challenge
prop-fr:titre
Minimum Vertex Cover PACE 2019
prop-fr:url
n10:node10.html n15:
dbo:thumbnail
n12:Couverture_de_sommets.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Problème_de_couverture_par_sommets
dbo:abstract
En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, Vertex Cover en anglais) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes. Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.
dbo:isPartOf
dbpedia-fr:21_problèmes_NP-complets_de_Karp