[comp.ai] What is `maximal clique' technique? - RESPOST

G.Joly@cs.ucl.ac.uk (Gordon Joly) (11/14/90)

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

G.Joly@cs.ucl.ac.uk (11/15/90)

Note in passing that Penrose discusses a related topic (to
cliques ) in "The Emperor's New Mind". In the chapter titled
"Truth, Proof and Insight" he reviews, P, NP and NP-completeness,
and give as an example (in graph theory), the complexity theory
concerned with a hamiltonian circuit.

G.Joly@cs.ucl.ac.uk (Gordon Joly) (11/15/90)

Note in passing that Penrose discusses a related topic (to cliques )
in "The Emperor's New Mind". In the chapter titled "Truth, Proof and
Insight" he reviews, P, NP and NP-completeness, and give as an example
(in graph theory), the complexity theory concerned with a Hamiltonian
circuit.


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