
University of Bonn > Department of Computer Science > Chair V  
CSAPXReports 2014  Copyright 2014 University of Bonn, Department of Computer Science, Abt. V  
89153 28.02.2014 
Approximate Counting of Matchings in (3,3)Hypergraphs
Andrzej Dudek, Marek Karpinski, Andrzej Rucinski and Edyta Szymanska [Download PostScript] [Download PDF] We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3uniform hypergraphs of maximum degree three, referred to as (3,3)hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3partite (3,3)hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest. 

Last Change:
11/05/14 at 11:06:36
Deutsch 
University of Bonn > Department of Computer Science > Chair V 