Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!axion!uzi-9mm.fulcrum.bt.co.uk!nott-cs!ucl-cs!news
From: G.Joly@cs.ucl.ac.uk (Gordon Joly)
Newsgroups: comp.ai
Subject: Re: What is `maximal clique' technique? - RESPOST
Message-ID: <1282@ucl-cs.uucp>
Date: 14 Nov 90 12:34:56 GMT
Sender: news@cs.ucl.ac.uk
Lines: 75


REPOST - RESPOST - REPOST - RESPOST - REPOST - RESPOST - REPOST - RESPOST

>From: kerisit@tic.world (JeanMarc.Kerisit)
>
>I'm also interested in any technique to determine the maximal clique(s) in a
>graph. If you have any information, please send it to me as well; Thanks in
>advance, 
>
>+------------------------------+------------------------------------------+
>| Jean-Marc Kerisit            | EMail : JeanMarc.Kerisit@cediag.bull.fr  |
>| BULL CEDIAG                  |    or                   kerisit@bull.fr  |
>| 68, Route de Versailles      |    or    ...!mcvax!inria!bullfr!kerisit  |
>| F-78430 Louveciennes FRANCE  |                                          |
>+------------------------------+------------------------------------------+

A clique is already maximal. A clique is a maximal complete sub-graph.
See, for example,

%A S. L. Lauritzen
%A D. J. Spiegelhalter
%T Local Computations with Probabilities on Graphical Structures and
their Application to Expert Systems
%J Journal of the Royal Statistical Society, Series B
%V 50
%N 2
%D 1988
%P 157-224

which has an AI flavour.

For a mathematical definition of clique, see page 20 of

%A Harary, Frank
%T Graph theory 
%C Reading (Mass)
%I Addison-Wesley
%D 1969
%P 274

For a fast algorithm see

%A Bron, Coen
%A Kerbosch, Joep
%T Algorithm 457: Finding all Cliques of an Undirected Graph [H]
%J Comm. ACM.
%V 16
%N 9
%D 1973
%P 575-577

and other algorithms can be found in

%A Tarjan, R. E.
%A Yannadikakis, M.
%T Simple linear-time algorithms to test chordality of graphs, test
acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs
%J SIAM J. Computing
%V 13
%D 1984
%P 566-579

Clique extraction can also be performed by a maximal cardinality
search, but note that a graph has to be triangulated and the fill-ins
are NP-hard to calculate. See,
 
%A Yannadikakis, M.
%T Computing the minimal fill-in is NP complete,
%J SIAM J. Algebraic Discrete Methods
%P 77-79
%D 1981

Gordon Joly                                           +44 71 387 7050 ext 3716
InterNet: G.Joly@cs.ucl.ac.uk       UUCP: ...!{uunet.uu.net,ukc}!ucl-cs!G.Joly
Computer Science, University College London, Gower Street, LONDON WC1E 6BT, UK