|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-APX-Reports 2012 | Copyright 2012 Universität Bonn, Institut für Informatik, 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |