Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/82290

Título:	Approximating the permanent is in RNC
Autor/a:	Díaz Cort, Josep; Serna Iglesias, María José; Spirakis, Paul George
Otros autores:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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 give a RNC almost uniform generator for perfect matchings in dense bipartite graphs, and its RNC reduction to its counting problem. As a consequence we can classify the problem of getting an approximation scheme to the permanent of a boolean matrix in RNC. We also state other problems for which the same technique applies.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica -Parallelization -Markov chain -RNC
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Mostrar el registro completo del ítem