Movatterモバイル変換


[0]ホーム

URL:


Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of theComputational Complexity Foundation (CCF)

Login|Register|Classic Style
iconSubmit Paper


RSS-Feed

REPORTS > DETAIL:

Paper:

TR14-065 | 2nd May 2014 09:40

Approximate Counting of Matchings in $(3,3)$-Hypergraphs

Contact
Add Comment
RSS-Feed

Abstract:

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform 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 3-partite $(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.



ISSN 1433-8092 |Imprint

[8]ページ先頭

©2009-2025 Movatter.jp