Approximating the directed path partition problem

DOI10.1016/j.ic.2024.105150OpenAlexW4391019870WikidataQ129716500 ScholiaQ129716500MaRDI QIDQ6204168

An Zhang, Curtis Kennedy, Yong Chen, Guo-Hui Lin, Zhi-Zhong Chen, Unnamed Author

Publication date: 27 March 2024

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2024.105150

zbMATH Keywords

digraphapproximation algorithmpath partitionalternating walkpath-cycle coverenlarging walk

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• A parameterized perspective on packing paths of length two
• Packings by cliques and by finite families of graphs
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• Approximation algorithms for the test cover problem
• A boundary class for the \(k\)-path partition problem
• Maximum skew-symmetric flows and matchings
• Kernels for packing and covering problems
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• An improved approximation algorithm for the minimum 3-path partition problem
• Packing paths: recycling saves time
• The path partition problem and related problems in bipartite graphs
• Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
• On Local Search for Weighted k-Set Packing
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• On the Complexity of General Graph Factor Problems
• 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
• 8/7-approximation algorithm for (1,2)-TSP
• Star Partitions of Perfect Graphs
• Paths, Trees, and Flowers
• STACS 2005
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• Approximation algorithms and hardness results for the clique packing problem

This page was built for publication: Approximating the directed path partition problem