An approximation algorithm for maximum packing of 3-edge paths

DOI10.1016/S0020-0190(97)00097-5zbMATH Open1337.68291MaRDI QIDQ287133FDOQ287133

Authors: Refael Hassin, Shlomi Rubinstein 

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

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

Cites Work

• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• `` Strong NP-Completeness Results
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Title not available (Why is that?)
• 25 pretty graph colouring problems

Cited In (18)

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

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)