.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for non-sequential star packing problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.ic.2025.105397.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
For a positive integer k >= 1, a k-star (k(+)-star, k(-)-star, respectively) is a connected graph containing a degree-& ell; vertex and & ell; degree-1 vertices, where & ell; = k (& ell; >= k, 1 <= & ell; <= k, respectively). The k(+)-star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k(+)-stars in G; and given k > t >= 1, the k(-)/t-star packing problem is to cover as many vertices of G as possible using vertex-disjoint k(-)stars but no t-stars in G. Both problems are NP-hard for any fixed k >= 2. We present a (1 + k(2)/ 2k+1 )- and a 3/ 2 -approximation algorithms for the k(+)-star packing problem when k >= 3 and k = 2, respectively, and a (1 + 1 /t+1+1/k )-approximation algorithm for the k(-)/t-star packing problem when k > t >= 2. They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively. (c) 2025 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Star packing
Local search
Amortization
Alternating path
Approximation algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
1
Papers:
79
Citations:
2.8K