Name
Abstract | ||
|---|---|---|
In this work we present a fully randomized approximation scheme for counting the number of perfect matchings in a dense bipartite graphs, that is equivalent to get a fully randomized approximation scheme to the permanent of a dense boolean matrix. We achieve this known solution, through novel extensions in the theory of suitable non-reversible, Markov chains which mix rapidly and have a near-uniform distribution. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0304-3975(97)00297-1 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
random generation,dense graph,Markov chains,Approximate counting,Matchings,Random generation | Journal | 201 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 65 | 7.03 |
| M. Serna | 2 | 31 | 4.28 |
| P. Spirakis | 3 | 113 | 15.66 |