Improved approximation algorithms for weighted 2-path partitions

DOI10.1016/J.DAM.2017.11.031MaRDI QIDQ1706113zbMATH OpenOpenAlexFDO

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

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

approximation algorithmsgraph partitioninggraph packinggraph factor

Mathematics Subject Classification ID

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

Recommendations

• Improved approximation algorithms for weighted 2-path partitions
• A local search algorithm for binary maximum 2-path partitioning
• An improved approximation algorithm for the minimum 3-path partition problem
• Algorithms – ESA 2004
• The P k Partition Problem and Related Problems in Bipartite Graphs

Cites work

• scientific article; zbMATH DE number 5999574 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1262785 (Why is no real title available?)
• scientific article; zbMATH DE number 2011853 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• A local search algorithm for binary maximum 2-path partitioning
• An approximation algorithm for maximum packing of 3-edge paths
• An approximation algorithm for maximum triangle packing
• An improved randomized approximation algorithm for maximum triangle packing
• Erratum to ``An approximation algorithm for maximum triangle packing
• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
• Looking at the stars
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and 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
• On the complexity of some edge-partition problems for graphs
• Packing triangles in low degree graphs and indifference graphs
• Packings by Complete Bipartite Graphs
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.

Cited in

(9)

• Improved approximation algorithms for cycle and path packings
• A deterministic approximation algorithm for metric triangle packing
• An improved approximation algorithm for metric triangle packing
• An improved approximation algorithm for the minimum 3-path partition problem
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance
• A local search algorithm for binary maximum 2-path partitioning
• Approximation algorithms for the maximum-weight cycle/path packing problems
• Improved approximation algorithms for weighted 2-path partitions

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

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