solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看169次
Counting perfect matchings and the switch chain. (arXiv:1705.05790v1 [cs.DM])
来源于:arXiv
We examine the problem of exactly or approximately counting all perfect
matchings in hereditary classes of nonbipartite graphs. In particular, we
consider the switch Markov chain of Diaconis, Graham and Holmes. We determine
the largest hereditary class for which the chain is ergodic, and define a large
new hereditary class of graphs for which it is rapidly mixing. We go on to show
that the chain has exponential mixing time for a slightly larger class. We also
examine the question of ergodicity of the switch chain in a arbitrary graph.
Finally, we give exact counting algorithms for three classes. 查看全文>>