| 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
| |
| dbo:wikiPageLength
|
- 7612 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:auteur
|
- Viggo Kann (fr)
- Viggo Kann (fr)
|
| prop-fr:consultéLe
| |
| prop-fr:date
|
- 2019 (xsd:integer)
- 2000-03-20 (xsd:date)
|
| prop-fr:langue
| |
| 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 | |