Scholarlink

In this chapter, we introduce the shortest path interdiction problems on trees under different norms. We put forward two primal-dual algorithms both in \(O(n^2)\) time to solve the (budget constrained) shortest path interdiction problem by upgrading edges under \(l_1\) norm on trees. Additionally, we show that the problems under weighted sum Hamming distance are \(\mathcal {N}\mathcal {P}\) -hard and propose two dynamic programming algorithms within \(O(n^4)\) and \(O(n^4\log n)\) time for their unit norm cases, respectively.

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

Shortest Path Interdiction Problems on Trees

  • 章节

  • 发表日期：

    2025年

查看全文
  • Xiucui Guan,
  • Panos M. Pardalos,
  • Binwu Zhang

摘要

In this chapter, we introduce the shortest path interdiction problems on trees under different norms. We put forward two primal-dual algorithms both in \(O(n^2)\) time to solve the (budget constrained) shortest path interdiction problem by upgrading edges under \(l_1\) norm on trees. Additionally, we show that the problems under weighted sum Hamming distance are \(\mathcal {N}\mathcal {P}\) -hard and propose two dynamic programming algorithms within \(O(n^4)\) and \(O(n^4\log n)\) time for their unit norm cases, respectively.