Improved Parameterized Algorithms for Weighted 3-Set Packing

摘要：

Packing problems form an important class of NP-hard problems. For the weighted 3-Set Packing problem, we provide further theoretical study on the problem and present a deterministic algorithm of time O*(10.63k). Based on the randomized divide-and-conquer method, the above result can be further reduced to O* (7.563k), which significantly improves the previous best result O*(12.83k).

作者: Jianxin Wang Qilong Feng

作者单位: School of Information Science and Engineering, Central South University,Changsha 410083, P.R. China

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 130-139

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）