A local search algorithm for binary maximum 2-path partitioning

DOI10.1016/J.DISOPT.2013.09.001MaRDI QIDQ1799391zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Ohad Schneider

Publication date 18 October 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2013.09.001

zbMATH Keywords

analysis of algorithms2-edge pathsmaximum path partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Improved approximation algorithms for weighted 2-path partitions
• Improved approximation algorithms for weighted 2-path partitions
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• The P k Partition Problem and Related Problems in Bipartite Graphs
• An improved approximation algorithm for the minimum 3-path partition problem

Cites work

• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305405 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• 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
• Approximation algorithms for the test cover problem
• Approximation results for the weighted \(P_4\) partition problem
• Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems
• How many disjoint 2-edge paths must a cubic graph have?
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• 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 \(k\)-path partition of graphs.
• P-Complete Approximation Problems
• The path partition problem and related problems in bipartite graphs

Cited in

(6)

• Improved approximation algorithms for cycle and path packings
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
• Improved approximation algorithms for weighted 2-path partitions
• Improved approximation algorithms for weighted 2-path partitions

This page was built for publication: A local search algorithm for binary maximum 2-path partitioning

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