Abstract | ||
---|---|---|
Let e, e; e2, e;...; el, el;... be a sequence of ordered pairs of edges chosen uniformly atrandom from the edge set of the complete graph Ks (i.e. we sample with replacement). Thissequence is used to form a graph by choosing at stage i, i ---- 1,..., one edge from el, eti tobe an edge in the graph, where the choice at stage i is based only on the observation of theedges that have appeared by stage i. We show that these choices can be made so that whp the size of the largest component... |
Year | DOI | Venue |
---|---|---|
2001 | 10.1002/rsa.1019 | Random Struct. Algorithms |
Keywords | Field | DocType |
giant component,complete graph | Discrete mathematics,Strength of a graph,Combinatorics,Line graph,Multigraph,Edge contraction,Cycle graph,Null graph,Mathematics,Complement graph,Path graph | Journal |
Volume | Issue | ISSN |
19 | 1 | 1042-9832 |
Citations | PageRank | References |
26 | 3.16 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Alan M. Frieze | 2 | 4837 | 787.00 |