Approximation algorithms for the directed path partition problems

DOI10.1007/978-3-030-97099-4_2zbMath1528.68280arXiv2107.04699OpenAlexW3181985263MaRDI QIDQ6113908

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

Publication date: 10 August 2023

Published in: Frontiers of Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.04699

zbMATH Keywords

digraphmatchingapproximation algorithmaugmenting pathpath partitionpath-cycle cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Approximation algorithms for the directed path partition problems ⋮ A local search algorithm for the \(k\)-path partition problem

Cites Work

• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• A boundary class for the \(k\)-path partition problem
• Maximum skew-symmetric flows and matchings
• 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
• The path partition problem and related problems in bipartite graphs
• Reducibility among Combinatorial Problems
• Approximation algorithms for the directed path partition problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for the directed path partition problems