.png){kind=icon}
返回
Approximation algorithms for the maximum path cover problem using long paths
.png){kind=icon}
OA
AI
DOI：10.1016/j.ic.2025.105378.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文研究的问题是：在给定图G = (V, E)中寻找一组顶点不相交的路径，使得每条路径的长度至少为k（称为长路径），并且这些路径上的边总数最大化。该问题对于任何固定的k或当k作为输入时，通过哈密尔顿路径问题的归约被证明是NP难的。Berman和Karpinski提出了k=1时的7/6-近似算法，但对于一般的k≥2，目前尚无直接针对该问题的近似算法。我们提出了首个针对任何固定k≥1的局部搜索（0.4394k + O(1)）-近似算法，以及基于最大无三角形路径-环覆盖的k=2时的1.4254-近似算法。
Keyword:
Path cover
Path-cycle cover
Local search
Recursion
Approximation algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
1
论文数:
79
被引数:
2.8K
机构
查看更多机构
引用论文
A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographscographs上k-固定端点路径覆盖问题的线性时间算法.png)
Networks
NetworksIF0
PREAI
分享收藏A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs关于在正常区间图上的k-固定端点路径覆盖问题的多项式解
PREAI
分享收藏Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph最小非平凡路径的路径覆盖及其在带冲突图的两机流水车间调度中的应用
PREAI
分享收藏分享收藏 没有更多内容