Show simple item record

dc.contributor.advisor Huber, Mark L en_US
dc.contributor.author Law, Wai Jing en_US
dc.date.accessioned 2009-05-01T18:00:28Z
dc.date.available 2009-05-01T18:00:28Z
dc.date.issued 2009 en_US
dc.identifier.uri http://hdl.handle.net/10161/1054
dc.description Dissertation en_US
dc.description.abstract <p>We develop algorithms to approximately count perfect matchings in bipartite graphs (or permanents of the corresponding adjacency matrices), perfect matchings in nonbipartite graphs (or hafnians), and general matchings in bipartite and nonbipartite graphs (or matching generating polynomials). </p><p>First, we study the problem of approximating the permanent and generating weighted perfect matchings in bipartite graphs from their correct distribution. We present a perfect sampling algorithm using self-reducible acceptance/rejection and an upper bound for the permanent. It has a polynomial expected running time for a class of dense problems, and it gives an improvement in running time by a factor of $n^3$ for matrices that are (.6)-dense. </p><p>Next, we apply the similar approach to study perfect matchings in nonbipartite graphs and also general matchings in general graphs. Our algorithms here have a subexponential expected running time for some classes of nontrivial graphs and are competitive with other Markov chain Monte Carlo methods.</p> en_US
dc.format.extent 878987 bytes
dc.format.mimetype application/pdf
dc.language.iso en_US
dc.subject Mathematics en_US
dc.subject acceptance en_US
dc.subject rejection en_US
dc.subject hafnian en_US
dc.subject matchings en_US
dc.subject Monte Carlo algorithms en_US
dc.subject permanent en_US
dc.title Approximately Counting Perfect and General Matchings in Bipartite and General Graphs en_US
dc.type Dissertation en_US
dc.department Mathematics en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record