Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Clique_problem> ?p ?o }
- 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 a maximum clique (largest clique by 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 Vol26.html.
- Clique_problem wikiPageExternalLink karp.pdf.
- Clique_problem wikiPageExternalLink 1817.
- Clique_problem wikiPageExternalLink Groger_1992_ActaCybernetica.pdf.
- Clique_problem wikiPageExternalLink techrep.html.
- Clique_problem wikiPageExternalLink 1935-01.pdf.
- Clique_problem wikiPageExternalLink match2007.pdf.
- Clique_problem wikiPageExternalLink 8p1980dfmrt3agyp.
- Clique_problem wikiPageExternalLink m64ju7clmqhqmv9g.
- Clique_problem wikiPageExternalLink p9qbl6y1v5t3xc1w.
- Clique_problem wikiPageExternalLink vlclq.html.
- Clique_problem wikiPageExternalLink cook.html.
- Clique_problem wikiPageExternalLink Halldorsson00.4.1.pdf.
- Clique_problem wikiPageExternalLink An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf.
- Clique_problem wikiPageExternalLink maxclique.
- Clique_problem wikiPageID "249254".
- Clique_problem wikiPageLength "64763".
- Clique_problem wikiPageOutDegree "195".
- Clique_problem wikiPageRevisionID "682808542".
- Clique_problem wikiPageWikiLink AND_gate.
- Clique_problem wikiPageWikiLink Aanderaa–Karp–Rosenberg_conjecture.
- Clique_problem wikiPageWikiLink Academic_Press.
- Clique_problem wikiPageWikiLink Acta_Mathematica.
- Clique_problem wikiPageWikiLink Adiabatic_quantum_computation.
- Clique_problem wikiPageWikiLink Adjacency_matrix.
- Clique_problem wikiPageWikiLink Algorithm.
- Clique_problem wikiPageWikiLink Algorithmica.
- Clique_problem wikiPageWikiLink American_Mathematical_Society.
- Clique_problem wikiPageWikiLink And_gate.
- Clique_problem wikiPageWikiLink Approximation_algorithm.
- Clique_problem wikiPageWikiLink Approximation_ratio.
- Clique_problem wikiPageWikiLink Arboricity.
- Clique_problem wikiPageWikiLink Backtracking.
- Clique_problem wikiPageWikiLink Best,_worst_and_average_case.
- Clique_problem wikiPageWikiLink Big_O_notation.
- Clique_problem wikiPageWikiLink Bioinformatics.
- Clique_problem wikiPageWikiLink Bipartite_graph.
- Clique_problem wikiPageWikiLink Boolean_satisfiability_problem.
- Clique_problem wikiPageWikiLink Boxicity.
- Clique_problem wikiPageWikiLink Branch_and_bound.
- Clique_problem wikiPageWikiLink Bron–Kerbosch_algorithm.
- Clique_problem wikiPageWikiLink Brute-force_search.
- Clique_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Clique_problem wikiPageWikiLink Category:NP-complete_problems.
- Clique_problem wikiPageWikiLink Chordal_graph.
- Clique_problem wikiPageWikiLink Circle_graph.
- Clique_problem wikiPageWikiLink Circuit_complexity.
- Clique_problem wikiPageWikiLink Clique.
- Clique_problem wikiPageWikiLink Clique_(graph_theory).
- Clique_problem wikiPageWikiLink Closure_(mathematics).
- Clique_problem wikiPageWikiLink Combinatorica.
- Clique_problem wikiPageWikiLink Communications_of_the_ACM.
- Clique_problem wikiPageWikiLink Complement_(graph_theory).
- Clique_problem wikiPageWikiLink Complement_graph.
- Clique_problem wikiPageWikiLink Complete_graph.
- Clique_problem wikiPageWikiLink Complete_multipartite_graph.
- Clique_problem wikiPageWikiLink Computational_chemistry.
- Clique_problem wikiPageWikiLink Computational_complexity_theory.
- Clique_problem wikiPageWikiLink Computer_science.
- Clique_problem wikiPageWikiLink Conjunctive_normal_form.
- Clique_problem wikiPageWikiLink Constraint_programming.
- Clique_problem wikiPageWikiLink Cook–Levin_theorem.
- Clique_problem wikiPageWikiLink Coppersmith–Winograd_algorithm.
- Clique_problem wikiPageWikiLink DIMACS.
- Clique_problem wikiPageWikiLink DNA_computing.
- Clique_problem wikiPageWikiLink Decision_problem.
- Clique_problem wikiPageWikiLink Decision_tree_complexity.
- Clique_problem wikiPageWikiLink Decision_tree_model.
- Clique_problem wikiPageWikiLink Degeneracy_(graph_theory).
- Clique_problem wikiPageWikiLink Dense_graph.
- Clique_problem wikiPageWikiLink Discrete_Mathematics_(journal).
- Clique_problem wikiPageWikiLink Dynamic_programming.
- Clique_problem wikiPageWikiLink Edge_(graph_theory).
- Clique_problem wikiPageWikiLink Erdős–Rényi_model.
- Clique_problem wikiPageWikiLink European_Symposium_on_Algorithms.
- Clique_problem wikiPageWikiLink Exponential_time.
- Clique_problem wikiPageWikiLink Exponential_time_hypothesis.
- Clique_problem wikiPageWikiLink Fan-in.
- Clique_problem wikiPageWikiLink File:Monotone_circuit_for_3-clique.svg.
- Clique_problem wikiPageWikiLink Finite_set.
- Clique_problem wikiPageWikiLink Glossary_of_graph_theory.
- Clique_problem wikiPageWikiLink Graph_(mathematics).
- Clique_problem wikiPageWikiLink Graph_minor.
- Clique_problem wikiPageWikiLink Graph_property.
- Clique_problem wikiPageWikiLink Greedy_algorithm.
- Clique_problem wikiPageWikiLink Hardness_of_approximation.
- Clique_problem wikiPageWikiLink Hereditary_property.
- Clique_problem wikiPageWikiLink Heuristic_(computer_science).
- Clique_problem wikiPageWikiLink Heuristic_algorithm.
- Clique_problem wikiPageWikiLink Independent_set_(graph_theory).
- Clique_problem wikiPageWikiLink Independent_set_problem.
- Clique_problem wikiPageWikiLink Induced_subgraph.
- Clique_problem wikiPageWikiLink Intelligent_Water_Drops_algorithm.
- Clique_problem wikiPageWikiLink Interval_graph.
- Clique_problem wikiPageWikiLink Introduction_to_the_Theory_of_Computation.
- Clique_problem wikiPageWikiLink Inverter_(logic_gate).
- Clique_problem wikiPageWikiLink Isolated_vertex.
- Clique_problem wikiPageWikiLink Journal_of_Computer_and_System_Sciences.