Approximation algorithms for non-sequential star packing problems

DOI10.1016/J.IC.2025.105397MaRDI QIDQ6865540zbMATH OpenFDO

Authors Mengyuan Hu, An Zhang, Yong Chen, Mingyang Gong, Guohui Lin

Publication date 2 February 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105397

zbMATH Keywords

approximation algorithmlocal searchalternating pathamortizationstar packing

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 5999574 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An approximation algorithm for covering vertices by \(4^+\)-paths
• An improved approximation algorithm for covering vertices by 4^+-paths
• An improved approximation for maximum weighted \(k\)-set packing
• Approximating the k-set packing problem by local improvements
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• Approximation algorithms for covering vertices by long paths
• Approximation algorithms for covering vertices by long paths
• Approximation algorithms for the k^+-star packing problem
• Efficient subgraphs packing
• Generalized planar matching
• How many disjoint 2-edge paths must a cubic graph have?
• How to sell hyperedges: the hypermatching assignment problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Maximum skew-symmetric flows and matchings
• On Restricted Two-Factors
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• On star family packing of graphs
• On the Complexity of General Graph Factor Problems
• Packing 2- and 3-stars into cubic graphs
• Packing triangles in bounded degree graphs.
• Packing triangles in low degree graphs and indifference graphs
• Packings by Complete Bipartite Graphs
• Packings by cliques and by finite families of graphs
• Path cover problems with length cost
• 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 limits of local search for weighted k-set packing
• The maximum 3-star packing problem in claw-free cubic graphs
• The path partition problem and related problems in bipartite graphs

This page was built for publication: Approximation algorithms for non-sequential star packing problems

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