Show simple item record

dc.contributor.advisorRamachandran, Vijayaen
dc.creatorFernholz, Daniel Turrin, 1976-en
dc.date.accessioned2008-08-28T23:56:29Zen
dc.date.available2008-08-28T23:56:29Zen
dc.date.issued2007-12en
dc.identifier.urihttp://hdl.handle.net/2152/3576en
dc.description.abstractThis 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.en
dc.format.mediumelectronicen
dc.language.isoengen
dc.rightsCopyright © 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.en
dc.subject.lcshRandom graphsen
dc.titleSparse random graphs methods, structure, and heuristicsen
dc.description.departmentComputer Sciencesen
dc.identifier.oclc192103500en
dc.type.genreThesisen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Sciencesen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record