2.0 | 1 rating Rate this file 143 downloads (last 30 days) File Size: 6.69 KB File ID: #19889

Maximal Cliques

12 May 2008 (Updated 02 Dec 2008)

finds all the maximal complete sub-graphs in a graph

File Information

Description

The graph passed must be an upper rectangular square matrix. Each row of a matrix denotes the presence of an edge with 1, and an absence of it with 0. The row and col no. of an edge denotes the connecting nodes. Given this matrix, this function finds all the maximal complete sub-graph (a set of nodes amongst all the nodes which form a complete sub-graph i.e. every node connects to every other) also known as cliques. A maximal graph is returned since every complete sub-graph will also have smaller complete sub-graphs inside itself. NOTE: this function would not return single node sub-graphs, although every isolated node, in concept, also forms a complete sub-graph.

The function returns all the sub-graphs in a cell-array, where each row denotes a new sub-graph

MATLAB release

MATLAB 7.5 (R2007b)

Tags for This File
Everyone's Tags	clique, complete subgraph, rectangular, square
Tags I've Applied
Add New Tags	Please login to tag files.

Comments and Ratings (2)
02 Dec 2008	Henry Wolkowicz	I have only tested the file a few times. It works well, but there should be a warning that it slows down quickly, i.e. 40 nodes can already be too much. Of course, finding all the cliques is an NP-hard problem so that is not a surprise. But, ... a warning would help.
07 Dec 2008	Ahmad	@Henry Warning added and the no. of nodes can be set by WARNING_CONNECTING_NODES_LENGTH .... which defaults to 20. I have done this since an NP-hard problem's actual computability would vary from machine to machine

Please login to add a comment or rating.

Updates
14 Aug 2008	Fixed critical bug
02 Dec 2008	Bug in nchoosek, while looping to get connecting nodes. Plus put a warning if a large computation is given for nchoosek

Public Submission Policy

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Disclaimer prior to use.