The maximum residual flow problem:: NP-hardness with two-arc destruction

被引：10

作者：

Du, Donglei ^{[1
]}

Chandrasekaran, R.

机构：

[1] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada

[2] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA

来源：

NETWORKS | 2007年 / 50卷 / 03期

关键词：

arc destruction; residual flow; NP-hard; capacity representative;

D O I：

10.1002/net.20188

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The maximum residual flow problem with one-arc destruction is shown to be solvable in strongly polynomial time in [Aneja et al., Networks, 38 (2001), 194-198]. However, the status of the corresponding problem with more than one-arc destruction is left open therein. We resolve the status of the two-arc destruction problem by demonstrating that it is already NP-hard. (c) 2007 Wiley Periodicals, Inc.

引用

页码：181 / 182

页数：2