Show simple item record

dc.contributor.authorXue, Mei
dc.date.accessioned2014-03-03T20:01:01Z
dc.date.available2014-03-03T20:01:01Z
dc.date.issued2001-05
dc.identifier.otherxue_mei_200105_ms
dc.identifier.urihttp://purl.galileo.usg.edu/uga_etd/xue_mei_200105_ms
dc.identifier.urihttp://hdl.handle.net/10724/20188
dc.description.abstractThis thesis explores randomized algorithms for _nding Hamilton cycles in cubic graphs.|After giving some basic de_nitions, we discuss an algorithm for generating random 3-regular graphs. This is used for testing. Then two approaches for _nding Hamilton cycles in random cubic graphs are presented, a random permutation method and a Markov chain method. Finally, we compare the performance of these two approaches and describe a backtracking algorithm for checking the hamil- tonicity of a graph. The latter can be applied to graphs of modest size for which the randomized algorithms can not _nd a Hamilton cycle.
dc.publisheruga
dc.rightspublic
dc.subjectHamilton Graph
dc.subjectPerfect Matching
dc.subjectRandomized Algorithm
dc.subjectCubic Graph
dc.subjectMarkov Chain
dc.subjectHamiltonian Graph
dc.titleFinding Hamilton cycles in cubic graphs
dc.typeThesis
dc.description.degreeMS
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorRobert Robinson
dc.description.committeeRobert Robinson
dc.description.committeeRodney Canfield
dc.description.committeeDaniel Everett


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record