|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Approximate Counting of Matchings in Sparse Uniform Hypergraphs | | Marek Karpinski
; Andrzej Rucinski
; Edyta Szymanska
; | | Date: |
24 Apr 2012 | | Abstract: | In this paper we give a fully polynomial randomized approximation scheme
(FPRAS) for the number of matchings in k-uniform hypergraphs whose intersection
graphs contain few claws. Our method gives a generalization of the canonical
path method of Jerrum and Sinclair to hypergraphs satisfying a local
restriction. Our proof method depends on an application of the Euler tour
technique for the canonical paths of the underlying Markov chains. On the other
hand, we prove that it is NP-hard to approximate the number of matchings even
for the class of k-uniform, 2-regular and linear hypergraphs, for all k >= 6,
without the above restriction. | | Source: | arXiv, 1204.5335 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER