An $$O^{*}(1.4366^n)$$ O ∗ ( 1. 4366 n ) -time exact algorithm for maximum $$P_2$$ P 2 -packing in cubic graphs

Maw-Shang Chang (), Li-Hsuan Chen () and Ling-Ju Hung ()
Additional contact information
Maw-Shang Chang: HungKuang University
Li-Hsuan Chen: National Chung Cheng University
Ling-Ju Hung: HungKuang University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 2, No 15, 594-607

Abstract: Abstract Given a graph $$G=(V, E)$$ G = ( V , E ) , a $$P_2$$ P 2 -packing $$\mathcal {P}$$ P is a collection of vertex disjoint copies of $$P_2$$ P 2 s in $$G$$ G where a $$P_2$$ P 2 is a simple path with three vertices and two edges. The Maximum $$P_2$$ P 2 -Packing problem is to find a $$P_2$$ P 2 -packing $$\mathcal {P}$$ P in the input graph $$G$$ 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 $$P_2$$ P 2 -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.4366^n)$$ O ∗ ( 1 . 4366 n ) which is faster than previous known exact algorithms where $$n$$ n is the number of vertices in the input graph.

Keywords: $$P_2$$ P 2 -packing; Cubic graphs; Branch-and-reduce algorithms; Measure-and-conquer (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9884-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:2:d:10.1007_s10878-015-9884-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9884-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().