Vertex cover (original) (raw)
V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny. Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož je maximální párování grafu.
| Property | Value |
|---|---|
| dbo:abstract | V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny. Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož je maximální párování grafu. (cs) Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig. (de) En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto. El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo. La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings. (es) 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) Di dalam disiplin matematika tentang teori graf, tutup verteks (bahasa Inggris: vertex cover) adalah himpunan simpul (vertex) di mana di setiap busur (edge) setidaknya dicakup oleh satu simpul (vertex) dari himpunan. Permasalahan yang ditemukan adalah bagaimana mencari vertex cover yang jumlahnya minimum. Permasalahan ini termasuk permasalahan optimasi yang sulit (Hard Problem) dalam ilmu komputer. (in) In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme S dei nodi di un grafo G=(V,E) tale che tutti gli archi in E abbiano almeno un estremo in S. Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo. (it) In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory. The minimum vertex cover problem can be formulated as a half-integral, linear program whose dual linear program is the maximum matching problem. Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs. (en) Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, assieme al problema del commesso viaggiatore, il knapsack problem, ecc. Questa classe di problemi è detta NP-completo, si dice cioè che il vertex cover o problema di copertura dei vertici è un problema NP-completo. È utile al riguardo la dimostrazione di equivalenza fra tutti i problemi NP-completo, come premesso. Mediante questi problemi si ottengono, ad esempio, modelli per la logistica o per il calcolo delle spese nella produzione. Il problema complementare al vertex-cover è detto copertura degli spigoli o edge cover. In informatica, il problema di copertura tramite vertici è un problema NP-completo e fu uno dei 21 problemi NP-completi di Richard Karp. È spesso usato in complessità computazionale per dimostrare l'NP-completezza di problemi più complicati. (it) 最小頂点被覆問題（さいしょうちょうてんひふくもんだい）は、計算複雑性理論におけるNP困難な問題の一つ。 問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′ |
| dbo:thumbnail | wiki-commons:Special:FilePath/Couverture_de_sommets.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.springer.com/east/home/generic/search/results%3FSGWID=5-40109-22-141358322-0 https://www.youtube.com/watch%3Fv=ZCVAGb1ee8A http://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf https://archive.org/details/introductiontoal00corm_691/page/n1046 http://erikdemaine.org/papers/HMinorFree_JACM/ http://www.cas.mcmaster.ca/~gk/papers/vc.pdf http://portal.acm.org/citation.cfm%3Fid=803884 https://books.google.com/books%3Fid=IMmuF0RZk1MC&pg=PA169 |
| dbo:wikiPageID | 562782 (xsd:integer) |
| dbo:wikiPageLength | 20563 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1101365979 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Metabolic_engineering dbr:Annals_of_Mathematics dbr:Approximation_algorithm dbr:Cubic_graph dbr:Vertex_cover_in_hypergraphs dbr:Decision_problem dbr:Independent_set_(graph_theory) dbr:Kőnig's_theorem_(graph_theory) dbc:NP-complete_problems dbr:Complement_(set_theory) dbr:Complete_bipartite_graph dbr:Clique_problem dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:NP-hard dbr:Closed-circuit_television dbr:Computational_complexity_theory dbr:Computer_science dbr:Half-integer dbr:PCP_theorem dbr:Synthetic_biology dbr:Tibor_Gallai dbr:Dual_linear_program dbr:Irit_Dinur dbr:Karp's_21_NP-complete_problems dbr:Linear_programming_relaxation dbr:Edge_(graph_theory) dbr:Graph_theory dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_the_ACM dbr:Repeated_sequence_(DNA) dbr:Covering_problems dbr:Hypergraph dbr:Fixed-parameter_tractable dbr:ACM_Transactions_on_Algorithms dbr:APX dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbc:Covering_problems dbr:Boolean_satisfiability_problem dbr:Planar_graph dbr:Polynomial_time dbr:Mihalis_Yannakakis dbr:Brute-force_search dbr:Optimization_problem dbr:Klam_value dbr:Mathematical_model dbr:Shmuel_Safra dbr:Unique_games_conjecture dbr:Vertex_(graph_theory) dbr:Exponential_time_hypothesis dbr:NP-completeness dbr:Maximal_matching dbr:Maximum_matching_problem dbr:Integer_linear_program dbr:Parameterized_complexity dbr:Linear_program dbr:Tree_graph dbr:Hard_to_approximate dbr:P_=_NP_problem dbr:P_≠_NP dbr:Polynomial-time dbr:Constant-factor_approximation_algorithm dbr:File:Couverture_de_sommets.svg dbr:File:Minimum-vertex-cover.svg dbr:File:Vertex-cover-from-maximal-matching.svg dbr:File:Vertex-cover.svg |
| dbp:title | Vertex Cover (en) Minimum Vertex Cover (en) Vertex Cover Number (en) |
| dbp:urlname | MinimumVertexCover (en) VertexCover (en) VertexCoverNumber (en) |
| dbp:wikiPageUsesTemplate | dbt:ECCC dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Commons_category dbt:MathWorld dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Covering-Packing_Problem_Pairs |
| dcterms:subject | dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory dbc:Covering_problems |
| gold:hypernym | dbr:Set |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Difficulty114408086 yago:Event100029378 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Problem114410605 yago:Procedure101023820 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720 yago:WikicatAlgorithms |
| rdfs:comment | V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny. Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož je maximální párování grafu. (cs) Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig. (de) En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto. El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo. La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings. (es) 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) Di dalam disiplin matematika tentang teori graf, tutup verteks (bahasa Inggris: vertex cover) adalah himpunan simpul (vertex) di mana di setiap busur (edge) setidaknya dicakup oleh satu simpul (vertex) dari himpunan. Permasalahan yang ditemukan adalah bagaimana mencari vertex cover yang jumlahnya minimum. Permasalahan ini termasuk permasalahan optimasi yang sulit (Hard Problem) dalam ilmu komputer. (in) In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme S dei nodi di un grafo G=(V,E) tale che tutti gli archi in E abbiano almeno un estremo in S. Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo. (it) 最小頂点被覆問題（さいしょうちょうてんひふくもんだい）は、計算複雑性理論におけるNP困難な問題の一つ。 問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′ |
| rdfs:label | Vrcholové pokrytí (cs) Knotenüberdeckung (de) Knotenüberdeckungsproblem (de) Cobertura de vértices (es) Tutup verteks (in) Problème de couverture par sommets (fr) Problema di copertura dei vertici (it) Copertura dei vertici (it) 最小頂点被覆問題 (ja) 頂点被覆 (ja) Knopenbedekking (nl) Problem pokrycia wierzchołkowego (pl) Pokrycie wierzchołkowe (pl) Cobertura de vértices (teoria dos grafos) (pt) Задача о вершинном покрытии (ru) Vertex cover (en) Вершинное покрытие (ru) 覆盖 (图论) (zh) Вершинне покриття (uk) |
| owl:sameAs | freebase:Vertex cover yago-res:Vertex cover wikidata:Vertex cover wikidata:Vertex cover dbpedia-cs:Vertex cover dbpedia-de:Vertex cover dbpedia-de:Vertex cover dbpedia-es:Vertex cover dbpedia-fa:Vertex cover dbpedia-fa:Vertex cover dbpedia-fr:Vertex cover dbpedia-he:Vertex cover dbpedia-id:Vertex cover dbpedia-it:Vertex cover dbpedia-it:Vertex cover dbpedia-ja:Vertex cover dbpedia-ja:Vertex cover dbpedia-nl:Vertex cover dbpedia-pl:Vertex cover dbpedia-pl:Vertex cover dbpedia-pt:Vertex cover dbpedia-ru:Vertex cover dbpedia-ru:Vertex cover dbpedia-sr:Vertex cover dbpedia-tr:Vertex cover dbpedia-uk:Vertex cover dbpedia-zh:Vertex cover https://global.dbpedia.org/id/D4P3 |
| prov:wasDerivedFrom | wikipedia-en:Vertex_cover?oldid=1101365979&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Couverture_de_sommets.svg wiki-commons:Special:FilePath/Minimum-vertex-cover.svg wiki-commons:Special:FilePath/Vertex-cover-from-maximal-matching.svg wiki-commons:Special:FilePath/Vertex-cover.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Vertex_cover |
| is dbo:wikiPageRedirects of | dbr:Vertex_Cover dbr:Vertex_cover_number dbr:Vertex_cover_problem dbr:Applications_of_vertex_cover_optimization dbr:Vertex_covering_number dbr:Covering_by_vertex_cover dbr:Min-cover dbr:Minimal_cover dbr:Minimum_cover dbr:Minimum_vertex_cover dbr:Vertex-cover_problem dbr:Vertex_covering dbr:Vertex_covering_problem dbr:Node_cover dbr:Node_cover_problem |
| is dbo:wikiPageWikiLink of | dbr:Bipartite_double_cover dbr:Approximation_algorithm dbr:Cubic_graph dbr:Vertex_Cover dbr:Vertex_cover_number dbr:Vertex_cover_problem dbr:Independent_set_(graph_theory) dbr:Integer_programming dbr:Kőnig's_theorem_(graph_theory) dbr:Matching_(graph_theory) dbr:Matching_in_hypergraphs dbr:Maximal_independent_set dbr:Geometric_set_cover_problem dbr:Odd_cycle_transversal dbr:Frankl–Rödl_graph dbr:Glossary_of_graph_theory dbr:Boxicity dbr:Connectomics dbr:Constraint_composite_graph dbr:Applications_of_vertex_cover_optimization dbr:Line_graph dbr:Feedback_vertex_set dbr:Kernelization dbr:Planar_separator_theorem dbr:Mathematical_chess_problem dbr:Avner_Magen dbr:Well-covered_graph dbr:Local_search_(optimization) dbr:Iterative_compression dbr:List_of_NP-complete_problems dbr:Sexual_dimorphism dbr:Covering_graph dbr:Wiener_connector dbr:APX dbr:Bidimensionality dbr:Blocking_set dbr:Edge_cover dbr:George_Nemhauser dbr:Holographic_algorithm dbr:Polygon_covering dbr:Metric_dimension_(graph_theory) dbr:Klam_value dbr:Unique_games_conjecture dbr:Vertex_(graph_theory) dbr:Exponential_time_hypothesis dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Vertex_covering_number dbr:River_crossing_puzzle dbr:Nondeterministic_constraint_logic dbr:Parameterized_complexity dbr:Twin-width dbr:Sperner_family dbr:Covering_by_vertex_cover dbr:Min-cover dbr:Minimal_cover dbr:Minimum_cover dbr:Minimum_vertex_cover dbr:Vertex-cover_problem dbr:Vertex_covering dbr:Vertex_covering_problem dbr:Node_cover dbr:Node_cover_problem |
| is foaf:primaryTopic of | wikipedia-en:Vertex_cover |
