CSCA67H3 Lecture 4: Week 4 - Cliques and 3SAT, Proof by Induction.pdf
21 Oct 2013
School
Department
Course
Professor
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:
