Re: Re: maximum clique algorithm

David,

Thanks for your reference; I look forward to reading same.
I'm working with reasonably small graphs, between
50 and 100 vertices.

Maximal complete subgraphs, correct.

Concerning density, that is a question that gets at the heart of the
matter.  Consider a (potentially) complete graph with N vertices and
(N*N-N)/2 edges.  Consider the edges weighted, and sorted by weight.
Start with N vertices and no edges.  Now insert the edges one by one.
After each insertion enumerate all maximal cliques (i.e., all maximal
complete subgraphs).  Of Course after you insert all edges you have a
completely dense graph.

For my problem I don't know at the outset how many edges I'm going
to insert in the graph.  But I do need to know, after every insertion,
the complete listing of all maximal cliques.

Yes, I would be interested in looking at your code.  Due to the
conditions of my employment, I'm not free to share my own solution
to my problem until I clear certain administrative hurdles.  But I
think it's pretty simple.

- regards, David

On Mon, 22 Nov 2004, David Eppstein wrote:

> In article <[email protected]>,
>  David Hysom <[email protected]> wrote:
>
> > I'm working on a bioinformatics problem, in the course of which I found
> > I needed
> > an algorithm to enumerate all cliques in a series of graphs.  Since I
> > couldn't find
> > any algorithm/implementation I liked, I designed an algorithm from
> > scratch (computes
> > exact answer, not heuristic).  I later realized the algorithm is
> > amenable to parallelization.
> >
> > I've looked around the web a bit, and haven't found an algorithm that's
> > similar to what
> > I came up with.  If any of you have expertise in this area to the extent
> > that you can
> > judge the novelty of my design, please write and I'll furnish further
> > details.
> >
> > - thanks David Hysom
> > Center for Applied Scientific Computing (CASC)
> > Lawrence Livermore Nat. Lab.
>
> What size graphs and what size cliques are you searching for?
> By clique you mean maximal complete subgraph, not just complete
> subgraph, right?  The problem is equivalent to searching for all maximal
> independent sets in the complement graph, of course.
>
> I have a recent paper on the subject at
> http://arxiv.org/abs/cs.DS/0407036
> and a Python implementation of one of the algorithms from that paper
> which I'd be happy to email you.
>
> But (from the point of view of listing cliques) that algorithm is tuned
> for relatively small but dense graphs. You can do better for sparse
> graphs e.g. by removing vertices one at a time, lowest degree vertex
> first, and finding cliques in the neighborhood of each removed vertex.
>
> --
> David Eppstein
> Computer Science Dept., Univ. of California, Irvine
> http://www.ics.uci.edu/~eppstein/
>
> _______________________________________________
> Csc mailing list
> Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
> http://list.odu.edu/listinfo/csc
>