Improved approximation algorithms for weighted 2-path partitions

DOI10.1016/J.DAM.2017.11.031zbMath1382.05056OpenAlexW2788624646MaRDI QIDQ1706113

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

Publication date: 21 March 2018

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

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

zbMATH Keywords

graph partitioningapproximation algorithmsgraph packinggraph factor

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

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
• Erratum to ``An approximation algorithm for maximum triangle packing
• 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
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• 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
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
• Packings by Complete Bipartite Graphs
• Star Partitions of Perfect Graphs

This page was built for publication: Improved approximation algorithms for weighted 2-path partitions