uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Large cliques in a power-law random graph
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2010 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 47, no 4, 1124-1135 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we study the size of the largest clique omega(G(n, alpha)) in a random graph G(n, alpha) on n vertices which has power-law degree distribution with exponent alpha. We show that, for 'flat' degree sequences with alpha > 2, with high probability, the largest clique in G(n, alpha) is of a constant size, while, for the heavy tail distribution, when 0 < alpha < 2, omega(G (n, alpha)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, alpha) a large clique of size (1 - o(1))omega(G(n, alpha)) in polynomial time.

Place, publisher, year, edition, pages
2010. Vol. 47, no 4, 1124-1135 p.
Keyword [en]
Power-law random graph, clique, greedy algorithm
National Category
URN: urn:nbn:se:uu:diva-148611ISI: 000286958100018OAI: oai:DiVA.org:uu-148611DiVA: diva2:402476
Available from: 2011-03-08 Created: 2011-03-08 Last updated: 2011-03-08Bibliographically approved

Open Access in DiVA

No full text

By organisation
Department of Mathematics
In the same journal
Journal of Applied Probability

Search outside of DiVA

GoogleGoogle Scholar

Total: 109 hits
ReferencesLink to record
Permanent link

Direct link