Proposal: More robust consensus voting with diverse authority sets

[Nikita Borisov]

On Wed, Apr 2, 2008 at 3:58 AM, Peter Palfrader <peter at palfrader.org> wrote:
> For those reading along at home, such fully connected subgraphs as
>  written about in the procedure are called cliques.
>  See http://en.wikipedia.org/wiki/Clique_problem for a short overview.
>  Finding the maximum clique is an NP hard problem, but it might just
>  scale to up to our 20 nodes.  There is literature on how to solve it,
>  for instance Steven Murdoch found "An Exact Parallel Algorithm For The
>  Maximum Clique Problem" by  Panos M. Pardalos, Jonas Rappe, Mauricio
>  G.C. Resende - <URL:http://citeseer.ist.psu.edu/pardalos98exact.html>.

I've built a max-clique implementation before, and it worked well for
social network graphs on the order of 100, so 20 should be no problem
at all.

- Nikita
-- 
Nikita Borisov - http://www.crhc.uiuc.edu/~nikita/
Assistant Professor, Electrical and Computer Engineering
Tel: (217) 244-5385, Office: 460 CSL