A Parameterized Perspective on Packing Paths of Length Two

DOI10.1007/978-3-540-85097-7_6MaRDI QIDQ5505643zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Daniel Raible

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_6

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A parameterized perspective on packing paths of length two
• Packing paths: recycling saves time
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• An improved kernelization for \(P_{2}\)-packing
• Narrow sieves for parameterized paths and packings

Cites work

• An approximation algorithm for maximum packing of 3-edge paths
• An approximation algorithm for maximum triangle packing
• An efficient parameterized algorithm for m-set packing
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Approximation algorithms for the test cover problem
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• scientific article; zbMATH DE number 5725105 (Why is no real title available?)
• Improved algorithms for path, matching, and packing problems
• On the completeness of a generalized matching problem
• Parameterized and Exact Computation
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

Cited in

(13)

• Vertex and edge covers with clustering properties: Complexity and algorithms
• The parameterized complexity of the induced matching problem
• Parameterized complexity of \((A,\ell)\)-path packing
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• Packing paths: recycling saves time
• Randomized adaptive test cover
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• Deterministic versus randomized adaptive test cover
• Packings and 2-packings of A-paths
• A Problem Kernelization for Graph Packing
• Parameterized Complexity of $$(A,\ell )$$-Path Packing
• Shortest \((A+B)\)-path packing via hafnian
• A parameterized perspective on packing paths of length two

This page was built for publication: A Parameterized Perspective on Packing Paths of Length Two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5505643)