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.
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/3576 |
| Date | 28 August 2008 |
| Creators | Fernholz, Daniel Turrin, 1976- |
| Contributors | Ramachandran, Vijaya |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | electronic |
| Rights | Copyright © is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. |
Page generated in 0.0021 seconds