Title:A Linear Programming Approach to the Maximum Clique Problem


			   Earl R. Barnes
			    Georgia Tech
		   Email:ebarnes@isye.gatech.edu
		   Web page:www.isye.gatech.edu

     Co-Authors: Joel Sokol, Dawn Strickland, Federico Trigos


Abstract:
We formulate a linear programming model whose solution gives an upper bound 
on the size of the largest clique in a graph G. For certain classes of 
perfect graphs the model computes a maximum clique exactly. For general 
graphs the model can be strengthened to compute a largest clique by adding 
certain nonlinear constraints. We describe some  approximation techniques 
for handling these nonlinear constraints.