An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs

DOI10.1007/s10878-015-9884-8zbMath1354.90104OpenAlexW271729878MaRDI QIDQ306106

Li-Hsuan Chen, Maw-Shang Chang, Ling-Ju Hung

Publication date: 31 August 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9884-8

zbMATH Keywords

cubic graphsmeasure-and-conquer\(P_2\)-packingbranch-and-reduce algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (1)

On maximum \(P_3\)-packing in claw-free subcubic graphs

Cites Work

• Improved deterministic algorithms for weighted matching and packing problems
• Exact exponential algorithms.
• Looking at the stars
• A parameterized perspective on packing paths of length two
• An improved kernelization for \(P_{2}\)-packing
• Maximum bounded \(H\)-matching is Max SNP-complete
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Narrow sieves for parameterized paths and packings
• The path partition problem and related problems in bipartite graphs
• Kernels for Packing and Covering Problems
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• On the completeness of a generalized matching problem
• Scheduling Split Intervals
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs