Name
Abstract | ||
|---|---|---|
Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S subset of or equal to V such that, for each vertex v is an element of V - S, the arc-connectivity from S to v is at least d(-)(v) and the arc-connectivity from v to S is at least d(+)(v). We present a polynomial time algorithm for the problem where d(-) and d(+) are uniformly fixed and w is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1080/1055-6780309510593 | OPTIMIZATION METHODS & SOFTWARE |
Keywords | Field | DocType |
graph algorithm,arc-connectivity,location problem,network flow,deficient set,tree hypergraph | Flow network,Graph algorithms,Mathematical optimization,Flow (psychology),Connectivity,Multi-commodity flow problem,Mathematics,Feedback arc set | Journal |
Volume | Issue | ISSN |
18 | 4 | 1055-6788 |
Citations | PageRank | References |
12 | 0.95 | 0 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Kazuhisa Makino | 2 | 1088 | 102.74 |
| Kouji Arata | 3 | 38 | 3.20 |
| Shoji Honami | 4 | 12 | 0.95 |
| Yuichiro Itatsu | 5 | 26 | 2.31 |
| Satoru Fujishige | 6 | 828 | 96.94 |