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