Sampling edge covers

Show simple item record

dc.contributor.advisor Bezakova, Ivona
dc.contributor.author Rummler, William August
dc.date.accessioned 2009-10-19T14:01:04Z
dc.date.available 2009-10-19T14:01:04Z
dc.date.issued 2009
dc.identifier.uri http://hdl.handle.net/1850/10647
dc.description.abstract The random generation or sampling of combinatorial objects has important applications to statistical analyses in various domains, including physics and evolutionary biology. Some objects whose sampling has been well-studied are contingency tables, matchings, and independent sets. Edge covers are related to matchings in graph theory; however, their association does not appear to be of the sort where results for sampling matchings imply results for sampling edge covers. Consequently, we investigate the sampling of edge covers and prove that efficiently sampling so-called (1,2)-edge covers is possible under reasonable restrictions.
dc.language.iso en_US
dc.subject Approximately uniform sampling en_US
dc.subject Canonical flow en_US
dc.subject Edge cover en_US
dc.subject Markov chain Monte Carlo en_US
dc.subject Random generation en_US
dc.subject Sampling en_US
dc.subject.lcc QA164.8 .R86 2009
dc.subject.lcsh Combinatorial enumeration problems
dc.subject.lcsh Graph theory
dc.title Sampling edge covers
dc.type Thesis
dc.description.college B. Thomas Golisano College of Computing and Information Sciences
dc.description.department Department of Computer Science
dc.contributor.advisorChair Bezakova, Ivona
dc.description.school Rochester Institute of Technology

Files in this item

Files Size Format View
26980_pdf_23833 ... 11DE-A618-273F9E1A67F9.pdf 283.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse