Improved Approximation Algorithms for Weighted 2-Path Partitions

DOI10.1007/978-3-662-48350-3_79zbMath1466.05175OpenAlexW2407583267MaRDI QIDQ3452854

Ivo Vigan, George Rabanca, Amotz Bar-Noy, David Peleg

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_79

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (2)

Local search algorithms for the maximum carpool matching problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
• Looking at the stars
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An improved randomized approximation algorithm for maximum triangle packing
• A local search algorithm for binary maximum 2-path partitioning
• On the complexity of some edge-partition problems for graphs
• Packing triangles in low degree graphs and indifference graphs
• An approximation algorithm for maximum triangle packing
• On Local Search for Weighted k-Set Packing
• 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
• An Improved Randomized Approximation Algorithm for Maximum Triangle Packing
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
• Packings by Complete Bipartite Graphs
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

This page was built for publication: Improved Approximation Algorithms for Weighted 2-Path Partitions