Improved approximation algorithms for weighted 2-path partitions
From MaRDI portal
Publication:1706113
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
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
