Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2012 Copyright 2012 University of Bonn, Department of Computer Science, Abt. V
89135

27.02.2012

Approximate Counting of Matchings in Sparse Hypergraphs
Marek Karpinski, Andrzej Rucinski and Edyta Szymanska
[Download PostScript] [Download PDF]

In this paper we give a fully polynomial randomized approximation scheme (FPRAS) for the number of all matchings in hypergraphs belonging to a class of sparse, uniform hypergraphs. Our method is based on a generalization of the canonical path method to the case of uniform hypergraphs.

Last Change: 11/05/14 at 11:01:02
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V