On Counting 3-D Matchings of Size k
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers and , and a given set S of n triples and an integer k, produces a number h in time O(5.48 3k n 2ln(2/)/ 2) such that [(1-epsilon)h-{0}leq hleq(1+epsilon)h-{0}]geq1-delta,where h 0 is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras. 2008 Springer Science+Business Media, LLC.