• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Feng Qilong, Wang Jianxin, and Chen Jianer. Improved Algorithms for Weighted 3D-Matching[J]. Journal of Computer Research and Development, 2009, 46(11): 1877-1884.
Citation: Feng Qilong, Wang Jianxin, and Chen Jianer. Improved Algorithms for Weighted 3D-Matching[J]. Journal of Computer Research and Development, 2009, 46(11): 1877-1884.

Improved Algorithms for Weighted 3D-Matching

More Information
  • Published Date: November 14, 2009
  • Matching problem is an important class of NP-hard problems, which has great applications in many fields, such as scheduling and code optimization etc. This paper mainly focuses on the weighted 3D-Matching problem, and gives further analysis for the structure of the problem. In order to solve the weighted 3D-Matching problem more efficiently, the weighted 3D-Matching problem is converted to the weighted 3D-Matching augmentation problem, which is to construct a maximum weighted (k+1)-matching based on a maximum weighted k-matching. The authors firstly provides further theoretical study on the structure of the weighted 3D-Matching augmentation problem and present some special properties of the problem. For the weighted 3D-Matching augmentation problem and for a given maximum weighted k-matching of the instance, there must exist two columns in this maximum weighted k-matching such that at least 2k/3 elements of those two columns are contained in the corresponding columns in maximum weighted (k+1)-matching. On the basis of those special properties and by using color-coding and dynamic programming techniques, an improved parameterized algorithm with time complexity O\+*(4.82\+[3k}) is given. The above improved algorithm results in an improved parameterized algorithm for the weighted 3D-Matching problem, which significantly improves the previous best result O\+*(5.47\+{3k}).

Catalog

    Article views (1012) PDF downloads (509) Cited by()
    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return