Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5301

Finding if a graph G contains any clique of size N...

From Richard Palmer <rhpalmer@gmail.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Finding if a graph G contains any clique of size N...
Date 2011-09-30 08:09 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j63tfk$6gv$1@smc.vnet.net> (permalink)

Show all headers | View raw


A b <http://en.wikipedia.org/wiki/Brute-force_search>rute force algorithm to
test whether a graph *G* contains a *k*-vertex clique, and to find any such
clique that it contains, is to examine each subgraph with at least *k* vertices
and check to see whether it forms a clique. This algorithm takes time O(*n**
k* *k*2):

Does Mathematica 8 have a straightforward algorithm to implement this that does not involve using the NP hard  FindClique?

-- 
Richard Palmer

Home                            941 412 8828
Cell                               508 982-7266
Business Internet Phone 941 882 0747

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread


Thread

Finding if a graph G contains any clique of size N... Richard Palmer <rhpalmer@gmail.com> - 2011-09-30 08:09 +0000

csiph-web