Approximation results for the weighted \(P_4\) partition problem

DOI10.1016/j.jda.2007.01.006zbMath1146.05315OpenAlexW2106588520MaRDI QIDQ935845

Sophie Toulouse, Jérôme Monnot

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.01.006

zbMATH Keywords

graph partitioningapproximation algorithmsperformance ratiodifferential approximationstandard approximation\(P_{4}\)-packing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Approximation of the double traveling salesman problem with multiple stacks ⋮ A local search algorithm for binary maximum 2-path partitioning

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• Differential approximation results for the traveling salesman and related problems
• Structure preserving reductions among convex optimization problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• On the \(k\)-path partition of graphs.
• The complexity of approximating a nonlinear program
• An approximation algorithm for maximum triangle packing
• z-Approximations
• 8/7-approximation algorithm for (1,2)-TSP
• P-Complete Approximation Problems
• Differential approximation of NP-hard problems with equal size feasible solutions
• The P k Partition Problem and Related Problems in Bipartite Graphs
• Approximations for minimum and min-max vehicle routing problems
• Fundamentals of Computation Theory

This page was built for publication: Approximation results for the weighted \(P_4\) partition problem