pith. sign in

arxiv: 1311.1091 · v2 · pith:T2TLD6SFnew · submitted 2013-11-05 · 🧮 math.PR · math.CO

The power of 2 choices over preferential attachment

classification 🧮 math.PR math.CO
keywords degreeattachmentchoicesgraphpreferentialprobabilityvertexachlioptas
0
0 comments X
read the original abstract

We introduce a new type of preferential attachment tree that includes choices in its evolution, like with Achlioptas processes. At each step in the growth of the graph, a new vertex is introduced. Two possible neighbor vertices are selected independently and with probability proportional to degree. Between the two, the vertex with smaller degree is chosen, and a new edge is created. We determine with high probability the largest degree of this graph up to some additive error term.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.