Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Clique_cover_problem> ?p ?o }
Showing triples 1 to 38 of
38
with 100 triples per page.
- Clique_cover_problem abstract "In computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper \"Reducibility Among Combinatorial Problems\".The clique cover problem (also sometimes called partition into cliques) is the problem of determining whether the vertices of a graph can be partitioned into k cliques. Given a partition of the vertices into k sets, it can be verified in polynomial time that each set forms a clique, so the problem is in NP. The NP-completeness of clique cover follows by reduction from GRAPH k-COLOURABILITY. To see this, first transform an instance G of GRAPH k-COLOURABILITY into its complement graph G'. A partition of G' into k cliques then corresponds to finding a partition of the vertices of G into k independent sets; each of these sets can then be assigned one colour to yield a k-colouring. The minimum k for which a clique cover exists is called the clique cover number of the given graph.The related clique edge cover problem considers sets of cliques that include all of the edges of a given graph. It is also NP-complete.".
- Clique_cover_problem wikiPageExternalLink karp.pdf.
- Clique_cover_problem wikiPageID "17113364".
- Clique_cover_problem wikiPageLength "2383".
- Clique_cover_problem wikiPageOutDegree "13".
- Clique_cover_problem wikiPageRevisionID "695750250".
- Clique_cover_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Clique_cover_problem wikiPageWikiLink Category:NP-complete_problems.
- Clique_cover_problem wikiPageWikiLink Clique_(graph_theory).
- Clique_cover_problem wikiPageWikiLink Complement_graph.
- Clique_cover_problem wikiPageWikiLink Computational_complexity_theory.
- Clique_cover_problem wikiPageWikiLink Graph_coloring.
- Clique_cover_problem wikiPageWikiLink Graph_theory.
- Clique_cover_problem wikiPageWikiLink Independent_set_(graph_theory).
- Clique_cover_problem wikiPageWikiLink Intersection_number_(graph_theory).
- Clique_cover_problem wikiPageWikiLink Karps_21_NP-complete_problems.
- Clique_cover_problem wikiPageWikiLink NP-completeness.
- Clique_cover_problem wikiPageWikiLink NP_(complexity).
- Clique_cover_problem wikiPageWikiLink Time_complexity.
- Clique_cover_problem wikiPageWikiLinkText "Clique cover problem".
- Clique_cover_problem wikiPageWikiLinkText "clique cover".
- Clique_cover_problem wikiPageUsesTemplate Template:Citation.
- Clique_cover_problem subject Category:Computational_problems_in_graph_theory.
- Clique_cover_problem subject Category:NP-complete_problems.
- Clique_cover_problem hypernym Problem.
- Clique_cover_problem type Disease.
- Clique_cover_problem comment "In computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper \"Reducibility Among Combinatorial Problems\".The clique cover problem (also sometimes called partition into cliques) is the problem of determining whether the vertices of a graph can be partitioned into k cliques.".
- Clique_cover_problem label "Clique cover problem".
- Clique_cover_problem sameAs Q1096734.
- Clique_cover_problem sameAs مسئله_پوشش_گروهک.
- Clique_cover_problem sameAs Problema_di_copertura_delle_cricche.
- Clique_cover_problem sameAs 最小クリーク被覆問題.
- Clique_cover_problem sameAs Cobertura_clique.
- Clique_cover_problem sameAs m.0421hlh.
- Clique_cover_problem sameAs Q1096734.
- Clique_cover_problem sameAs 分團覆蓋問題.
- Clique_cover_problem wasDerivedFrom Clique_cover_problem?oldid=695750250.
- Clique_cover_problem isPrimaryTopicOf Clique_cover_problem.