Sparse random graphs methods, structure, and heuristics

Date

2007-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.

Description

Keywords

Citation