.png){kind=icon}
返回
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}
分享.png){kind=icon}
收藏
摘要
En 中文
对于正整数k ≥ 1，一个k-星（k(+)-星、k(-)-星，分别对应）是一个包含度数为ℓ的顶点和ℓ个度数为1的顶点的连通图，其中ℓ = k (ℓ ≥ k, 1 ≤ ℓ ≤ k，分别对应)。k(+)-星填充问题是通过使用G中顶点不相交的k(+)-星尽可能多地覆盖输入图G的顶点；给定k > t ≥ 1，k(-)/t-星填充问题是通过使用G中顶点不相交的k(-)-星但不含t-星尽可能多地覆盖G的顶点。这两个问题对于任何固定的k ≥ 2都是NP难问题。我们分别针对k ≥ 3和k = 2时提出了(1 + k(2)/2k+1)-和3/2-近似算法用于k(+)-星填充问题，并针对k > t ≥ 2时提出了(1 + 1/t+1+1/k)-近似算法用于k(-)/t-星填充问题。它们都是局部搜索算法，并且分别改进了这些问题目前已知的最佳近似算法。(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/).
Keyword:
Star packing
Local search
Amortization
Alternating path
Approximation algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
1
论文数:
79
被引数:
2.8K
机构
.png){kind=icon}
查看更多内容