Abstract | ||
---|---|---|
AbstractWe consider the height of random k-trees and k-Apollonian networks. These random graphs are not really trees, but instead have a tree-like structure. The height will be the maximum distance of a vertex from the root. We show that w.h.p. the height of random k-trees and k-Apollonian networks is asymptotic to c log t, where t is the number of vertices, and c = ck is given as the solution to a transcendental equation. The equations are slightly different for the two types of process. In the limit as k ï ∞ the height of both processes is asymptotic to logt/klog2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 675-702, 2014 |
Year | DOI | Venue |
---|---|---|
2014 | 10.1002/rsa.20576 | Periodicals |
Keywords | Field | DocType |
Random k-trees,Random k-Apollonian networks | Discrete mathematics,Random element,Combinatorics,Random graph,Transcendental equation,Vertex (geometry),struct,Mathematics,Branching (version control) | Journal |
Volume | Issue | ISSN |
45 | 4 | 1042-9832 |
Citations | PageRank | References |
3 | 0.54 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colin Cooper | 1 | 857 | 91.88 |
Alan M. Frieze | 2 | 4837 | 787.00 |
Ryuhei Uehara | 3 | 528 | 75.38 |