Loading...
Loading...

Go to the content (press return)

On RNC approximate counting

Author
Diaz, J.; Serna, M.; Spirakis, P.G.
Type of activity
Report
Date
1994-11
Code
LSI-94-45-R
Repository
http://hdl.handle.net/2117/97212 Open in new window
Abstract
In this work we look into the parallelization (in the NC sense) of the Markov Chain approach to almost random generation (as described by Sinclair (1993)). We prove that for several problems rapid mixing is In this work we look into the parallelization (in the NC sense) of the Markov Chain approach to almost random generation (as described by Sinclair (1993)). We prove that for several problems rapid mixing is "equivalent" to RNC, but there are rapid mixing chains for which the method can not be...
Citation
Diaz, J., Serna, M., Spirakis, P.G. "On RNC approximate counting". 1994.
Keywords
Approximate counting, Parallelization, RNC, Rapid mixing
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments