Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Clique_problem> ?p ?o. }
Showing items 1 to 55 of
55
with 100 items per page.
- Clique_problem abstract "In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.For example, the maximum clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. To find a largest subset of people who all know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for social networks comprising more than a few dozen people. Although this brute-force search can be improved by more efficient algorithms, all of these algorithms take exponential time to solve the problem. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. Along with its applications in social networks, the clique problem also has many applications in bioinformatics and computational chemistry.Clique problems include: finding the maximum clique (a clique with the largest number of vertices),finding a maximum weight clique in a weighted graph,listing all maximal cliques (cliques that cannot be enlarged)solving the decision problem of testing whether a graph contains a clique larger than a given size.These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems), the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.".
- Clique_problem thumbnail Brute_force_Clique_algorithm.svg?width=300.
- Clique_problem wikiPageExternalLink cook.html.
- Clique_problem wikiPageExternalLink Vol26.html.
- Clique_problem wikiPageExternalLink Halldorsson00.4.1.pdf.
- Clique_problem wikiPageExternalLink karp.pdf.
- Clique_problem wikiPageExternalLink 1817.
- Clique_problem wikiPageExternalLink Groger_1992_ActaCybernetica.pdf.
- Clique_problem wikiPageExternalLink An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf.
- Clique_problem wikiPageExternalLink techrep.html.
- Clique_problem wikiPageExternalLink 1935-01.pdf.
- Clique_problem wikiPageExternalLink match2007.pdf.
- Clique_problem wikiPageExternalLink maxclique.
- Clique_problem wikiPageExternalLink 8p1980dfmrt3agyp.
- Clique_problem wikiPageExternalLink m64ju7clmqhqmv9g.
- Clique_problem wikiPageExternalLink p9qbl6y1v5t3xc1w.
- Clique_problem wikiPageExternalLink vlclq.html.
- Clique_problem wikiPageID "249254".
- Clique_problem wikiPageRevisionID "605227619".
- Clique_problem hasPhotoCollection Clique_problem.
- Clique_problem subject Category:Computational_problems_in_graph_theory.
- Clique_problem subject Category:NP-complete_problems.
- Clique_problem type Abstraction100002137.
- Clique_problem type Attribute100024264.
- Clique_problem type ComputationalProblemsInGraphTheory.
- Clique_problem type Condition113920835.
- Clique_problem type Difficulty114408086.
- Clique_problem type NP-completeProblems.
- Clique_problem type Problem114410605.
- Clique_problem type State100024720.
- Clique_problem comment "In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.For example, the maximum clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance.".
- Clique_problem label "Clique problem".
- Clique_problem label "Cliquenproblem".
- Clique_problem label "Problem kliki".
- Clique_problem label "Problema de la clique".
- Clique_problem label "Problema della cricca".
- Clique_problem label "Problema do clique".
- Clique_problem label "Задача о клике".
- Clique_problem label "مشكلة المخطط الكامل ضمن مخطط".
- Clique_problem label "分團問題".
- Clique_problem label "最大クリーク問題".
- Clique_problem sameAs Cliquenproblem.
- Clique_problem sameAs Problema_de_la_clique.
- Clique_problem sameAs Problema_della_cricca.
- Clique_problem sameAs 最大クリーク問題.
- Clique_problem sameAs 클릭_문제.
- Clique_problem sameAs Problem_kliki.
- Clique_problem sameAs Problema_do_clique.
- Clique_problem sameAs m.01k_tj.
- Clique_problem sameAs Q1196873.
- Clique_problem sameAs Q1196873.
- Clique_problem sameAs Clique_problem.
- Clique_problem wasDerivedFrom Clique_problem?oldid=605227619.
- Clique_problem depiction Brute_force_Clique_algorithm.svg.
- Clique_problem isPrimaryTopicOf Clique_problem.
