Statements (36)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:approximation |
hard to approximate
|
| gptkbp:category |
combinatorial optimization
graph |
| gptkbp:complementGraphRelation |
maximum independent set problem
|
| gptkbp:complexity |
NP-complete
|
| gptkbp:decision |
gptkb:clique_problem
|
| gptkbp:defines |
Given a graph, the problem of finding the largest clique (a subset of vertices such that every two vertices are connected by an edge).
|
| gptkbp:famousAlgorithm |
gptkb:Carraghan–Pardalos_algorithm
gptkb:Robson's_algorithm gptkb:Bron–Kerbosch_algorithm |
| gptkbp:field |
computer science
graph theory |
| gptkbp:formedBy |
1970s
|
| gptkbp:hardness |
gptkb:NP-hard
|
| https://www.w3.org/2000/01/rdf-schema#label |
maximum clique problem
|
| gptkbp:input |
graph
|
| gptkbp:optimizedFor |
gptkb:maximum_clique_problem
|
| gptkbp:output |
largest clique
|
| gptkbp:relatedTo |
gptkb:clique
gptkb:vertex_cover_problem graph NP-complete problem graph coloring problem maximum independent set problem |
| gptkbp:solvedBy |
heuristics
approximation algorithms exact algorithms |
| gptkbp:usedIn |
coding theory
computational chemistry computer vision bioinformatics social network analysis |
| gptkbp:bfsParent |
gptkb:clique
gptkb:Clique_problem |
| gptkbp:bfsLayer |
6
|