An improved approximation algorithm for the minimum k-star partition problem

DOI10.1007/978-981-95-0215-8_7MaRDI QIDQ6867289zbMATH OpenFDO

Authors Tong Xu, Wei Yu, Zhaohui Liu

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0215-8_7

zbMATH Keywords

approximation algorithmlocal searchpath partitionstar partition

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• \(k\)-path partitions in trees
• 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 local search algorithm for the k-path partition problem
• An improved approximation algorithm for the minimum 3-path partition problem
• Approximating the directed path partition problem
• Maximum skew-symmetric flows and matchings
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• On the Complexity of General Graph Factor Problems
• Packings by Complete Bipartite Graphs
• Reducibility among combinatorial problems
• The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time
• The path partition problem and related problems in bipartite graphs

This page was built for publication: An improved approximation algorithm for the minimum \(k\)-star partition problem

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