An approximation algorithm for maximum packing of 3-edge paths

DOI10.1016/S0020-0190(97)00097-5zbMath1337.68291MaRDI QIDQ287133

Shlomi Rubinstein, Refael Hassin

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithmsmaximum set packing

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) Approximation algorithms (68W25)

Related Items (16)

An approximation algorithm for the maximum traveling salesman problem ⋮ Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs ⋮ A parameterized perspective on packing paths of length two ⋮ Local improvement algorithms for a path packing problem: a performance analysis based on linear programming ⋮ Approximating the directed path partition problem ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Packing paths: recycling saves time ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ The path partition problem and related problems in bipartite graphs ⋮ An approximation algorithm for maximum triangle packing ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ Algorithms – ESA 2004 ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ A Parameterized Perspective on Packing Paths of Length Two ⋮ Approximating the maximum quadratic assignment problem

Cites Work

• `` Strong NP-Completeness Results
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• 25 pretty graph colouring problems
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Unnamed Item

This page was built for publication: An approximation algorithm for maximum packing of 3-edge paths