A parameterized perspective on packing paths of length two

DOI10.1007/s10878-009-9230-0zbMath1184.90136OpenAlexW2797447161MaRDI QIDQ849135

Daniel Raible, Henning Fernau

Publication date: 24 February 2010

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.611.1918

zbMATH Keywords

extremal combinatoricsparameterized algorithms

Mathematics Subject Classification ID

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

Related Items (17)

An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Parameterized approximation algorithms for packing problems ⋮ Narrow sieves for parameterized paths and packings ⋮ Local improvement algorithms for a path packing problem: a performance analysis based on linear programming ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Combinatorial search in two and more rounds ⋮ Approximating the directed path partition problem ⋮ Packing paths: recycling saves time ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Kernels for packing and covering problems ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ An improved kernelization for \(P_{2}\)-packing ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Unnamed Item ⋮ Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• Equivalence between the minimum covering problem and the maximum matching problem
• Approximation algorithms for the test cover problem
• Approximation algorithms for some vehicle routing problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• The \(k\)-feature set problem is \(W[2\)-complete]
• An approximation algorithm for maximum triangle packing
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• A Problem Kernelization for Graph Packing
• Parameterized and Exact Computation
• On the completeness of a generalized matching problem
• The P k Partition Problem and Related Problems in Bipartite Graphs
• A Parameterized Perspective on Packing Paths of Length Two
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• SOFSEM 2005: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science
• Algorithms and Data Structures

This page was built for publication: A parameterized perspective on packing paths of length two