Path: news.mathworks.com!not-for-mail
From: "Ahmad " <ahmad.humyn@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Graph Problem - Finding all sets of nodes forming complete sub-graphs
Date: Wed, 7 May 2008 19:20:14 +0000 (UTC)
Organization: University of Lahore
Lines: 30
Message-ID: <fvsvde$sb7$1@fred.mathworks.com>
Reply-To: "Ahmad " <ahmad.humyn@gmail.com>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1210188014 29031 172.30.248.38 (7 May 2008 19:20:14 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 7 May 2008 19:20:14 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 687196
Xref: news.mathworks.com comp.soft-sys.matlab:467235


Hi there,

I want to find all the sets of nodes in a graph which have
edges between all the nodes in the set....in other words I
want to find all the complete sub-graphs in an
un-directional graph: e.g.

If I have this upper-triangular graph (un-directed graph)
where each
edge is denoted by a 1 (0 is no edge) ... e.g. C is
connected to D:
    A    B    C    D    E    F
A   X    1    1    0    0    0
B   X    X    1    0    0    0
C   X    X    X    1    0    1
D   X    X    X    X    0    1
E   X    X    X    X    X    0
F   X    X    X    X    X    X

If I give the algo this matrix, it should return me two
answer sets -> (A,B,C) and (C,D,F).

Am I looking for finding cliques? If so what is the fastest
way known to compute these quickly? Anybody implemented this
on Matlab? What is the most standard easiest way to compute
these sets. I have heard cliques are 3-SAT (NP complete)?

Please help!!

Thanks