论文标题
两个播放器最短路径网络拦截问题
The two player shortest path network interdiction problem
论文作者
论文摘要
在本文中，我们研究了最短路径网络拦截问题的生物主体扩展。网络中的每个弧都与两个整数长度值相关联，两个播放器计算出各自的最短路径，从源到彼此独立下沉，而inctixtor试图通过删除弧线来延长这两个最短路径。我们表明这个问题是棘手的，并且决定可行的拦截策略是否有效，NP完整。我们提供了一个解决方案程序，以在假poly术时间中的两端串联平行图上解决问题。
In this article, we study a biobjective extension of the shortest path network interdiction problem. Each arc in the network is associated with two integer length values and two players compute their respective shortest paths from source to sink independently from each other while an interdictor tries to lengthen both shortest paths by removing arcs. We show that this problem is intractable and that deciding whether a feasible interdiction strategy is efficient, is NP- complete. We provide a solution procedure to solve the problem on two-terminal series-parallel graphs in pseudopolynomial time.
