k-edge-connectivity augmentation problem with upper bounds on edge multiplicity
説明
The k-edge-connectivity augmentation problem of a graph with upper bounds on edge multiplicity is defined as follows: "Given a graph G=(V, E) and a function f: V/spl times/V/spl rarr/Z/sup +/ (nonnegative integers), find an edge set of minimum cardinality among those sets E' such that G'=(V, E/spl cup/E') is k-edge-connected and, for any pair of vertices u, v, the number of edges added between u and v is no more than f(u, v)." In this paper, we first show that this problem is NP-complete. Then we propose three heuristic algorithms and compare their capability through experiment.
収録刊行物
-
- 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No.00CH36353)
-
2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No.00CH36353) 4 601-604, 2002-11-07
Presses Polytech. Univ. Romandes