DIMACS TR: 2006-10

Finding max-cliques in power-law graphs with large clique coefficients



Authors: James Abello and Michael Capalbo

ABSTRACT

Here we show that the Max-Clique problem is hard, even when restricted to sparse low-diameter power-law graphs with a large clustering coefficient.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-10.ps.gz
DIMACS Home Page