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.

Property Value
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. (fr)
  • 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. (fr)
dbo:isPartOf
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 2894443 (xsd:integer)
dbo:wikiPageLength
  • 7612 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 181353404 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:auteur
  • Viggo Kann (fr)
  • Viggo Kann (fr)
prop-fr:consultéLe
  • 2014-08-06 (xsd:date)
prop-fr:date
  • 2019 (xsd:integer)
  • 2000-03-20 (xsd:date)
prop-fr:langue
  • en (fr)
  • en (fr)
prop-fr:site
  • A compendium of NP optimization problems (fr)
  • Parameterized Algorithms and Computational Experiments Challenge (fr)
  • A compendium of NP optimization problems (fr)
  • Parameterized Algorithms and Computational Experiments Challenge (fr)
prop-fr:titre
  • Minimum Vertex Cover (fr)
  • PACE 2019 (fr)
  • Minimum Vertex Cover (fr)
  • PACE 2019 (fr)
prop-fr:url
prop-fr:wikiPageUsesTemplate
dct:subject
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. (fr)
  • 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. (fr)
rdfs:label
  • Задача о вершинном покрытии (ru)
  • Knotenüberdeckungsproblem (de)
  • Problema di copertura dei vertici (it)
  • Problème de couverture par sommets (fr)
  • 覆盖 (图论) (zh)
  • Задача о вершинном покрытии (ru)
  • Knotenüberdeckungsproblem (de)
  • Problema di copertura dei vertici (it)
  • Problème de couverture par sommets (fr)
  • 覆盖 (图论) (zh)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of