Approximating the directed path partition problem

DOI10.1016/J.IC.2024.105150MaRDI QIDQ6204168zbMATH OpenOpenAlexWikidataFDO

Authors Yong Chen, Zhi-Zhong Chen, Curtis Kennedy, Guohui Lin, An Zhang

Publication date 27 March 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

approximation algorithmdigraphpath partitionalternating walkpath-cycle coverenlarging walk

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• 8/7-approximation algorithm for (1,2)-TSP
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• A boundary class for the k-path partition problem
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• A parameterized perspective on packing paths of length two
• An approximation algorithm for maximum packing of 3-edge paths
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• An improved approximation algorithm for the minimum 3-path partition problem
• Approximation algorithms and hardness results for the clique packing problem
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• Approximation algorithms for the test cover problem
• Introduction to algorithms.
• Kernels for packing and covering problems
• Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
• Maximum skew-symmetric flows and matchings
• On local search for weighted \(k\)-set packing
• 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
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• Packing paths: recycling saves time
• Packings by cliques and by finite families of graphs
• Paths, Trees, and Flowers
• STACS 2005
• The path partition problem and related problems in bipartite graphs
• \(k\)-path partitions in trees

Cited in

(6)

• Directed path partition problem on directed acyclic graphs
• An improved approximation algorithm for the minimum k-star partition problem
• Improved approximation algorithms for the \(k\)-path partition problem
• Parameterizing path partitions
• An improved approximation algorithm for the minimum 4-star partition problem
• Path cover using only short paths

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

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