ON THE RANDOM GENERATION AND COUNTING OF MATCHINGS IN DENSE GRAPHS

Authors
DIAZ J SERNA M SPIRAKIS P
Citation
J. Diaz et al., ON THE RANDOM GENERATION AND COUNTING OF MATCHINGS IN DENSE GRAPHS, Theoretical computer science, 201(1-2), 1998, pp. 281-290
Citations number
11
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
201
Issue
1-2
Year of publication
1998
Pages
281 - 290
Database
ISI
SICI code
0304-3975(1998)201:1-2<281:OTRGAC>2.0.ZU;2-W
Abstract
In this work we present a fully randomized approximation scheme for co unting the number of perfect matchings in a dense bipartite graphs, th at 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, Mar kov chains which mix rapidly and have a near-uniform distribution. (C) 1998-Elsevier Science B.V. All rights reserved.