An O*(1.4366(n))-time exact algorithm for maximum P-2-packing in cubic graphs

作者：Chang Maw Shang; Chen Li Hsuan; Hung Ling Ju^*

来源：Journal of Combinatorial Optimization, 2016, 32(2): 594-607.

DOI：10.1007/s10878-015-9884-8

• P-2-packing
• Cubic graphs
• Branch-and-reduce algorithms
• Measure-and-conquer

Given a graph , a -packing is a collection of vertex disjoint copies of s in where a is a simple path with three vertices and two edges. The Maximum -Packing problem is to find a -packing in the input graph of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the Maximum -Packing problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time which is faster than previous known exact algorithms where is the number of vertices in the input graph.

• 出版日期2016-8