Scholarlink

This paper studies \(MPC^{5+}_v\) , which is to cover as many vertices as possible in a given graph \(G=(V,E)\) by vertex-disjoint \(5^+\) -paths (i.e., paths each with at least five vertices). \(MPC^{5+}_v\) is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of \(\frac{19}{7}\approx 2.714\) and runs in \(O(|V|^6)\) time. In this paper, we present a new approximation algorithm for \(MPC^{5+}_v\) which achieves a ratio of 2.511 and runs in \(O(\max \{|E|^2|V|^{2.5}, |E||V|^4\})\) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximately Covering Vertices by Order-5 or Longer Paths

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Mingyang Gong,
  • Zhi-Zhong Chen,
  • Guohui Lin,
  • Lusheng Wang

摘要

This paper studies \(MPC^{5+}_v\) , which is to cover as many vertices as possible in a given graph \(G=(V,E)\) by vertex-disjoint \(5^+\) -paths (i.e., paths each with at least five vertices). \(MPC^{5+}_v\) is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of \(\frac{19}{7}\approx 2.714\) and runs in \(O(|V|^6)\) time. In this paper, we present a new approximation algorithm for \(MPC^{5+}_v\) which achieves a ratio of 2.511 and runs in \(O(\max \{|E|^2|V|^{2.5}, |E||V|^4\})\) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion.