• 中国精品科技期刊
  • 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}).
  • Related Articles

    [1]Shi Haihe, Zhou Weixing. Design and Implementation of Pairwise Sequence Alignment Algorithm Components Based on Dynamic Programming[J]. Journal of Computer Research and Development, 2019, 56(9): 1907-1917. DOI: 10.7544/issn1000-1239.2019.20180835
    [2]Zhao Liang, Wang Yongli, Du Zhongshu, Chen Guangsheng. HL-DAQ: A Dynamic Adaptive Quantization Coding for Hash Learning[J]. Journal of Computer Research and Development, 2018, 55(6): 1294-1307. DOI: 10.7544/issn1000-1239.2018.20170238
    [3]Su Jindian, Yu Shanshan. Corecursive Operations with Parameters and the Associated Calculational Laws[J]. Journal of Computer Research and Development, 2013, 50(12): 2676-2690.
    [4]Yu Shanshan, Li Shixian, Su Jindian. Hylomorphisms with Parameters and Its Associated Calculational Laws[J]. Journal of Computer Research and Development, 2013, 50(3): 602-618.
    [5]Wang Kai, Hou Zifeng. An Adaptive Scheduling Method of Weight Parameter Adjustment on Virtual Machines[J]. Journal of Computer Research and Development, 2011, 48(11): 2094-2102.
    [6]Wang Jianxin, Xu Xiaoshuang, Feng Qilong, Li Min. An Exact Algorithm Based on Chain Indication for Min-CVCB Problem[J]. Journal of Computer Research and Development, 2008, 45(9): 1509-1516.
    [7]Qi Ji, Li Xi, Yu Haichen, Hu Nan, Gong Yuchang, Wang Ligang. A Scheduling Algorithm for Dynamic Reconfigurable Computing[J]. Journal of Computer Research and Development, 2007, 44(8): 1439-1447.
    [8]Yang Wenguo, Guo Tiande, Zhao Tong. Routing Algorithms of the Wireless Sensor Network Based on Dynamic Programming[J]. Journal of Computer Research and Development, 2007, 44(5): 890-897.
    [9]Wang Zhiming, Cai Lianhong, Ai Haizhou. Automatic Estimation of Visual Speech Parameters[J]. Journal of Computer Research and Development, 2005, 42(7): 1185-1190.
    [10]Zhang Min, Lin Chuan, and Ma Shaoping. Dynamic Parameter Learning Approach for Information Retrieval with Genetic Algorithm[J]. Journal of Computer Research and Development, 2005, 42(3).

Catalog

    Article views (1019) PDF downloads (510) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return