A Parameterized Perspective on Packing Paths of Length Two

DOI10.1007/978-3-540-85097-7_6zbMath1168.05358OpenAlexW1500219622MaRDI QIDQ5505643

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

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

Related Items (6)

A parameterized perspective on packing paths of length two ⋮ Deterministic versus randomized adaptive test cover ⋮ Randomized Adaptive Test Cover ⋮ A Problem Kernelization for Graph Packing ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ The parameterized complexity of the induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• Approximation algorithms for the test cover problem
• An approximation algorithm for maximum triangle packing
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• An efficient parameterized algorithm for m-set packing
• Parameterized and Exact Computation
• On the completeness of a generalized matching problem

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