Home // DBKDA 2011, The Third International Conference on Advances in Databases, Knowledge, and Data Applications // View article

MAXCLIQUE Problem Solved Using SQL

Authors:
Jose Torres-Jimenez
Nelson Rangel-Valdez
Himer Avila-George
Loreto Gonzalez-Hernandez

Keywords: Optimization; MAXCLIQUE; SQL query.

Abstract:
This paper aims to show that SQL queries can be used to solve a well-known combinatorial optimization problem, the Maximum Clique Problem (MAXCLIQUE). This problem arises in many real world applications as computer vision and pattern recognition or coding theory to mention some of them. A clique of a graph is a complete subgraph, i.e., a graph where every pair of vertices is an edge. The MAXCLIQUE problem searches for the clique of the largest cardinality in a graph (the one with the greatest number of nodes). We propose a model based on SQL queries to solve this problem. We test our models in 62 random instances. Results show that the use of simple queries can yield solutions for the MAXCLIQUE problem in an easy and accessible form.

Pages: 83 to 88

Copyright: Copyright (c) IARIA, 2011

Publication date: January 23, 2011

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-115-1

Location: St. Maarten, The Netherlands Antilles

Dates: from January 23, 2011 to January 28, 2011