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.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ