An approximation algorithm for maximum packing of 3-edge paths

DOI10.1016/S0020-0190(97)00097-5MaRDI QIDQ287133zbMATH OpenFDO

Authors Refael Hassin, Shlomi Rubinstein

Publication date 26 May 2016

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

Full work available at URL https://doi.org/10.1016/S0020-0190(97)00097-5

zbMATH Keywords

analysis of algorithmsmaximum set packing

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

Cites work

• 25 pretty graph colouring problems
• `` Strong NP-Completeness Results
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

Cited in

(23)

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

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

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