On Counting 3-D Matchings of Size k Academic Article uri icon

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.

published proceedings

  • Algorithmica

author list (cited authors)

  • Liu, Y., Chen, J., & Wang, J.

citation count

  • 2

complete list of authors

  • Liu, Yunlong||Chen, Jianer||Wang, Jianxin

publication date

  • August 2009