The minimum vulnerability problem on specific graph classes
The minimum vulnerability problem on specific graph classes
复制标题
DOI：
10.1007/s10878-015-9950-2
复制
发表时间：
2015-09
影响因子：
1
通讯作者：
Y. Aoki;B. Halldórsson;M. Halldórsson;Takehiro Ito;C. Konrad;Xiaoping Zhou
中科院分区：
文献类型：
--
作者：
Y. Aoki;B. Halldórsson;M. Halldórsson;Takehiro Ito;C. Konrad;Xiaoping Zhou
设无向图G的每条边对应三个非负整数，分别称为e的代价、脆弱性和容量。然后，我们考虑在G中寻找两个给定顶点之间总代价最小的路的问题，每条边可以被最多条路无代价地共享，如果我们付出代价，每条边可以被多条路共享，但即使我们付出代价，每条边也不能被多条路共享。该问题推广了无向图的不相交路问题、最小共享边问题和最小边费用流问题，是NP-困难的。本文从特定图类的角度研究了这一问题，并给出了三个结果。我们首先证明了这个问题是NP-困难的，即使是二部外平面图，2-树，图的路径宽度为2，完全二部图，完全图。然后，我们给出了一个伪多项式时间算法的有界树宽图。最后，我们给出了弦图的一个固定参数算法。
Suppose that each edgeeof an undirected graphGis associated with three nonnegative integers,and, called the cost, vulnerability and capacity ofe, respectively. Then, we consider the problem of findingpaths inGbetween two prescribed vertices with the minimum total cost; each edgeecan be shared without any cost by at mostpaths, and can be shared by more thanpaths if we pay, but cannot be shared by more thanpaths even if we pay the cost fore. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the numberof required paths.