CSCA67H3 Study Guide - Cluster Analysis, Data Mining, Mathematical Induction
6
CSCA67H3 Full Course Notes
Verified Note
6 documents
Document Summary
A clique in a graph is a set s of vertices such that ev- ery pair of vertices in s are adjacent. If the clique has n vertices, it is denoted by kn. Finding maximal sized cliques in large graphs is a challenging problem in data mining, i. e. , analyzing data clustering. Maximal clique detection arises in bioinformatics, analysis of so- cial networking patterns, web page clustering etc. Given a set of clauses c = {c1, c2, . 3, over a set of variables x = {x1, x2, . Consider the following algorithm to construct a graph from f : create a vertex for each literal in the formula. Use the literal to label the vertex: group the vertices corresponding to a clause together, connect two vertices in the graph if they are, in different clauses, and are not a negation of each other. The problem known as clique is the following:
