Path cover using only short paths

DOI10.1016/J.TCS.2025.115455MaRDI QIDQ6914023zbMATH OpenFDO

Authors Mingyang Gong, Guang-Ting Chen, Zhi-Zhong Chen, Guohui Lin, Riki Uchida

Publication date 17 October 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115455

zbMATH Keywords

2-piece packingapproximation algorithmpath coverpath partition

Mathematics Subject Classification ID

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

Cites work

• \(k\)-path partitions in trees
• 8/7-approximation algorithm for (1,2)-TSP
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• A local search algorithm for the k-path partition problem
• An approximation algorithm for covering vertices by \(4^+\)-paths
• An improved approximation algorithm for the minimum 3-path partition problem
• Approximating the directed path partition problem
• Approximation algorithms for covering vertices by long paths
• Combinatorial optimization. Theory and algorithms.
• Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
• Directed path partition problem on directed acyclic graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximation algorithms for the \(k\)-path partition problem
• Maximum ATSP with weights zero and one via half-edges
• Nontrivial path covers of graphs: existence, minimization and maximization
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• Path cover problems with length cost
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• The k‐piece packing problem
• The design of approximation algorithms
• The path partition problem and related problems in bipartite graphs

Cited in

(1)

• Approximately partitioning vertices into short paths

This page was built for publication: Path cover using only short paths

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