Sampling edge covers

Show simple item record

dc.contributor.advisor Bezakova, Ivona Rummler, William August 2009-10-19T14:01:04Z 2009-10-19T14:01:04Z 2009
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.relation RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
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 B. Thomas Golisano College of Computing and Information Sciences
dc.description.department Department of Computer Science
dc.contributor.advisorChair Bezakova, Ivona 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