Packing paths: recycling saves time

DOI10.1016/j.dam.2011.11.008zbMath1287.05112OpenAlexW2000071866MaRDI QIDQ2446295

Daniel Binkele-Raible, Henning Fernau

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.11.008

zbMATH Keywords

packingsextremal graph theoryparameterized algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Dealing with several parameterized problems by random methods ⋮ Approximating the directed path partition problem ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Arbitrary Overlap Constraints in Graph Packing Problems

Cites Work

• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• A parameterized perspective on packing paths of length two
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Approximation algorithms for the test cover problem
• Approximation algorithms for some vehicle routing problems
• Packing paths of length at least two
• 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
• 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
• Faster Algebraic Algorithms for Path and Packing Problems
• A Problem Kernelization for Graph Packing
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem
• The P k Partition Problem and Related Problems in Bipartite Graphs
• The k‐piece packing problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Packing paths: recycling saves time