Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

DOI10.1007/s10878-013-9691-zzbMath1327.90256OpenAlexW2042292124MaRDI QIDQ2354298

Qilong Feng, Jianxin Wang, Shao-hua Li, Jian'er Chen

Publication date: 10 July 2015

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

Full work available at URL: https://doi.org/10.1007/s10878-013-9691-z

zbMATH Keywords

randomized algorithm\(P_2\)-packingco-path packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (15)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Randomized parameterized algorithms for the kidney exchange problem ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Kernelization and randomized parameterized algorithms for co-path set problem ⋮ Approximating power node-deletion problems ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Kernels for packing and covering problems ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Cites Work

• Unnamed Item
• Looking at the stars
• A parameterized perspective on packing paths of length two
• Improved parameterized set splitting algorithms: A Probabilistic approach
• Approximation algorithms for the test cover problem
• An approximation algorithm for maximum triangle packing
• Matching and P 2-Packing: Weighted Versions
• A Linear Kernel for Co-Path/Cycle Packing
• Approximating Node-Deletion Problems for Matroidal Properties
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems