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

DOI10.1142/S0129054125400027MaRDI QIDQ7263277zbMATH OpenFDO

Authors Qilu Bao, Wei Yu, Zhaohui Liu, Yong Chen

Publication date 12 June 2026

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054125400027

zbMATH Keywords

approximation algorithmlocal searchpath partitionstar partition

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX)

Cites work

• 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 improved approximation algorithm for the minimum 3-path partition problem
• Approximating the directed path partition problem
• Maximum skew-symmetric flows and matchings
• On the Complexity of General Graph Factor Problems
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• Packings by Complete Bipartite Graphs
• The path partition problem and related problems in bipartite graphs
• \(k\)-path partitions in trees

This page was built for publication: An improved approximation algorithm for the minimum 4-star partition problem

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