Sparse random graphs methods, structure, and heuristics
Fernholz, Daniel Turrin, 1976-
MetadataShow full item record
This dissertation is an algorithmic study of sparse random graphs which are parametrized by the distribution of vertex degrees. Our contributions include: a formula for the diameter of various sparse random graphs, including the Erdös-Rényi random graphs G[subscript n,m] and G[subscript n,p] and certain power-law graphs; a heuristic for the k-orientability problem, which performs optimally for certain classes of random graphs, again including the Erdös-Rényi models G[subscript n,m] and G[subscript n,p]; an improved lower bound for the independence ratio of random 3-regular graphs. In addition to these structural results, we also develop a technique for reasoning abstractly about random graphs by representing discrete structures topologically.