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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, p. 1124-1135Article 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, p. 1124-1135
Keywords [en]
Power-law random graph, clique, greedy algorithm
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-148611ISI: 000286958100018OAI: oai:DiVA.org:uu-148611DiVA, id: diva2:402476
Available from: 2011-03-08 Created: 2011-03-08 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 336 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf