Approximation algorithms for the minimum weight cycle/path partition problem

DOI10.1007/S10878-026-01422-7MaRDI QIDQ7296594zbMATH OpenFDO

Authors Yaqi Li, Wei Yu, Zhaohui Liu

Publication date 14 July 2026

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-026-01422-7

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cites work

• 8/7-approximation algorithm for (1,2)-TSP
• A deterministic approximation algorithm for metric triangle packing
• A General Approximation Technique for Constrained Forest Problems
• A local search algorithm for binary maximum 2-path partitioning
• A randomized approximation algorithm for metric triangle packing
• An approximation algorithm for maximum packing of 3-edge paths
• Approximation algorithms for the maximum-weight cycle/path packing problems
• Approximation results for the weighted \(P_4\) partition problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximation algorithms for cycle and path packings
• Improved approximation algorithms for weighted 2-path partitions
• On the \(k\)-path partition of graphs.

This page was built for publication: Approximation algorithms for the minimum weight cycle/path partition problem

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