Given a graph G = (V, E), a P2-packing [Pscr ] is a collection of vertex disjoint copies of P2s in G where a P2 is a simple path with three vertices and two edges. The MAXIMUM P2-PACKING problem is to find a P2-packing [Pscr ] in the input graph G of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the MAXIMUM P2-PACKING problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O*(1.4366n) which is faster than previous known exact algorithms where n is the number of vertices in the input graph.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com