Efficient Fixed-parameter Enumeration Algorithm for the 3-D Matching Problem
Wang Jian-xin · 2010
Enumerating a number of good solutions to a problem has an increasing demand in recented research in computational science.In this paper,we presented a fixed-parameter enumeration algorithm for the 3-D Matching problem.More precisely,we developed an algorithm that,on a given set S of n weighted triples and two integers k and z,produces z best k-matchings in time O(5.483kkn2z).Our algorithm is based on the recent improved color-coding techniques and the fixed-parameter enumeration framework.This result shows that the 3-D Matching problem is fixed parameter linearly enumerable.