Inverse maximum capacity problems

被引：28

作者：

Yang C. ^{[1
]}

Zhang J. ^{[1
]}

机构：

[1] Department of Mathematics, City University of Hong Kong, Hong Kong

来源：

Operations-Research-Spektrum | 1998年 / 20卷 / 2期

关键词：

Inverse problems; Maximum capacity path; Maximum capacity tree; Minimum unrestricted cut set; Minimum weight cut set;

D O I：

10.1007/BF01539860

中图分类号：

学科分类号：

摘要：

Let E be a finite set, ℱ be a family of subsets of E and C̄ be a capacity vector for all elements of E. For each F ∈ ℱ, define the capacity of F as the minimum capacity occurring in F. The problem which we discuss in this paper is how to change the vector C̄ as little as possible so that a given F0 ∈ ℱ has the maximum capacity. This model contains inverse maximum capacity spanning tree problem, inverse maximum capacity path problem and etc. as its special cases. We transform the problem into the minimum weight cut set problem and show that this problem can be solved efficiently if an efficient algorithm for finding minimum weight cut set of ℱ is available. © Springer-Verlag 1998.

引用

页码：97 / 100

页数：3

共 12 条

[1]

Burton D., Toint P.L., On an instance of the inverse shortest paths problem, Mathematical Programming, 53, pp. 45-61, (1992)

[2]

Zhang J., Ma Z., Yang C., A column generation method for inverse shortest path problem, Zeitschrift für Operations Research, 41, pp. 347-358, (1995)

[3]

Xu S., Zhang J., An inverse problem of the weighted shortest path problem, Japan Journal of Industrial and Applied Mathematics, 12, pp. 47-60, (1995)

[4]

Zhang J., Liu Z., Ma Z., On the inverse problem of minimum spanning tree with partition constraints, Zeitschrift für Operations Research, 44, pp. 171-187, (1996)

[5]

Zhang J., Ma Z., A network flow method for solving some inverse combinatorial optimization problems, Optimization, 37, pp. 59-72, (1996)

[6]

Zhang J., Xu S., Ma Z., An algorithm for inverse minimum spanning tree problem, Optimization Methods and Software, (1998)

[7]

Sokkalingam P.T., Ahuja R.K., Orlin J.B., (1996)

[8]

Nagamochi H., Ibaraki T., Computing edge-connectivity in multigraphs and capacitated graphs, SIAM J Discrete Math, 5, pp. 54-66, (1992)

[9]

Hao J., Orlin J.B., A faster algorithm for finding the minimum cut in a directed graph, J Algorithms, 17, pp. 424-446, (1994)

[10]

Stoer M., Wagner F., A simple min cut problem, Proceedings of the 2nd European Symposium on Algorithms, (1994)

← 1 2 →