Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Vertex_cover> ?p ?o }
- Vertex_cover abstract "In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.The problem of finding a minimum vertex cover is a classical optimization problem in computer science and 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 thumbnail Vertex-cover.svg?width=300.
- Vertex_cover wikiPageExternalLink v=onepage&q=karpinski%20zelikovsky%20cover%20dense&f=false.
- Vertex_cover wikiPageExternalLink results?SGWID=5-40109-22-141358322-0.
- Vertex_cover wikiPageExternalLink HMinorFree_JACM.
- Vertex_cover wikiPageExternalLink citation.cfm?id=781528.
- Vertex_cover wikiPageExternalLink citation.cfm?id=803884.
- Vertex_cover wikiPageID "562782".
- Vertex_cover wikiPageLength "19987".
- Vertex_cover wikiPageOutDegree "80".
- Vertex_cover wikiPageRevisionID "678366741".
- Vertex_cover wikiPageWikiLink APX.
- Vertex_cover wikiPageWikiLink Annals_of_Mathematics.
- Vertex_cover wikiPageWikiLink Approximation_algorithm.
- Vertex_cover wikiPageWikiLink Bipartite_graph.
- Vertex_cover wikiPageWikiLink Boolean_satisfiability_problem.
- Vertex_cover wikiPageWikiLink Brute-force_search.
- Vertex_cover wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Vertex_cover wikiPageWikiLink Category:NP-complete_problems.
- Vertex_cover wikiPageWikiLink Clique_problem.
- Vertex_cover wikiPageWikiLink Complement_(set_theory).
- Vertex_cover wikiPageWikiLink Complete_bipartite_graph.
- Vertex_cover wikiPageWikiLink Computational_complexity_theory.
- Vertex_cover wikiPageWikiLink Computer_science.
- Vertex_cover wikiPageWikiLink Computers_and_Intractability.
- Vertex_cover wikiPageWikiLink Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness.
- Vertex_cover wikiPageWikiLink Constant-factor_approximation_algorithm.
- Vertex_cover wikiPageWikiLink Covering_problem.
- Vertex_cover wikiPageWikiLink Covering_problems.
- Vertex_cover wikiPageWikiLink Cubic_graph.
- Vertex_cover wikiPageWikiLink Decision_problem.
- Vertex_cover wikiPageWikiLink Dual_linear_program.
- Vertex_cover wikiPageWikiLink Duality_(optimization).
- Vertex_cover wikiPageWikiLink Exponential_time_hypothesis.
- Vertex_cover wikiPageWikiLink Fixed-parameter_tractable.
- Vertex_cover wikiPageWikiLink Graph_(mathematics).
- Vertex_cover wikiPageWikiLink Graph_theory.
- Vertex_cover wikiPageWikiLink Greedy_algorithm.
- Vertex_cover wikiPageWikiLink Half-integral.
- Vertex_cover wikiPageWikiLink Hypergraph.
- Vertex_cover wikiPageWikiLink Independent_set_(graph_theory).
- Vertex_cover wikiPageWikiLink Integer_linear_program.
- Vertex_cover wikiPageWikiLink Introduction_to_Algorithms.
- Vertex_cover wikiPageWikiLink Irit_Dinur.
- Vertex_cover wikiPageWikiLink Journal_of_Computer_and_System_Sciences.
- Vertex_cover wikiPageWikiLink Journal_of_the_ACM.
- Vertex_cover wikiPageWikiLink K-approximation_of_k-hitting_set.
- Vertex_cover wikiPageWikiLink Karps_21_NP-complete_problems.
- Vertex_cover wikiPageWikiLink Kxc3xb6nigs_theorem_(graph_theory).
- Vertex_cover wikiPageWikiLink Linear_program.
- Vertex_cover wikiPageWikiLink Linear_programming.
- Vertex_cover wikiPageWikiLink Linear_programming_relaxation.
- Vertex_cover wikiPageWikiLink Matching_(graph_theory).
- Vertex_cover wikiPageWikiLink Mathematics.
- Vertex_cover wikiPageWikiLink Maximal_matching.
- Vertex_cover wikiPageWikiLink Maximum_matching_problem.
- Vertex_cover wikiPageWikiLink Mihalis_Yannakakis.
- Vertex_cover wikiPageWikiLink NP-complete.
- Vertex_cover wikiPageWikiLink NP-completeness.
- Vertex_cover wikiPageWikiLink NP-hard.
- Vertex_cover wikiPageWikiLink NP-hardness.
- Vertex_cover wikiPageWikiLink Optimization_problem.
- Vertex_cover wikiPageWikiLink PCP_theorem.
- Vertex_cover wikiPageWikiLink P_=_NP_problem.
- Vertex_cover wikiPageWikiLink P_versus_NP_problem.
- Vertex_cover wikiPageWikiLink Parameterized_complexity.
- Vertex_cover wikiPageWikiLink Planar_graph.
- Vertex_cover wikiPageWikiLink Polynomial_time.
- Vertex_cover wikiPageWikiLink Race_condition.
- Vertex_cover wikiPageWikiLink Set_cover.
- Vertex_cover wikiPageWikiLink Set_cover_problem.
- Vertex_cover wikiPageWikiLink Shmuel_Safra.
- Vertex_cover wikiPageWikiLink Tibor_Gallai.
- Vertex_cover wikiPageWikiLink Time_complexity.
- Vertex_cover wikiPageWikiLink Tree_(graph_theory).
- Vertex_cover wikiPageWikiLink Tree_graph.
- Vertex_cover wikiPageWikiLink Unique_games_conjecture.
- Vertex_cover wikiPageWikiLink File:Minimum-vertex-cover.svg.
- Vertex_cover wikiPageWikiLink File:Vertex-cover-from-maximal-matching.svg.
- Vertex_cover wikiPageWikiLink File:Vertex-cover.svg.
- Vertex_cover wikiPageWikiLinkText "Min Vertex Cover".
- Vertex_cover wikiPageWikiLinkText "VC".
- Vertex_cover wikiPageWikiLinkText "Vertex Cover".
- Vertex_cover wikiPageWikiLinkText "Vertex cover".
- Vertex_cover wikiPageWikiLinkText "Vertex cover#Vertex cover in hypergraphs".
- Vertex_cover wikiPageWikiLinkText "linear program relaxation of vertex cover".
- Vertex_cover wikiPageWikiLinkText "vertex cover problem".
- Vertex_cover wikiPageWikiLinkText "vertex cover".
- Vertex_cover hasPhotoCollection Vertex_cover.
- Vertex_cover title "Minimum Vertex Cover".
- Vertex_cover title "Vertex Cover Number".
- Vertex_cover title "Vertex Cover".
- Vertex_cover urlname "MinimumVertexCover".
- Vertex_cover urlname "VertexCover".
- Vertex_cover urlname "VertexCoverNumber".
- Vertex_cover wikiPageUsesTemplate Template:Cite_book.
- Vertex_cover wikiPageUsesTemplate Template:Cite_journal.
- Vertex_cover wikiPageUsesTemplate Template:Covering-Packing_Problem_Pairs.
- Vertex_cover wikiPageUsesTemplate Template:MathWorld.
- Vertex_cover wikiPageUsesTemplate Template:Refbegin.