Name
Abstract | ||
|---|---|---|
Given an undirected multigraph G = (V, E) and requirement functions r
: (
2
) Z
+ and r
: (
2
) Z
+ (where Z
+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the edge-connectivity and vertex connectivity between every pair , V become at least r
(, ) and r
k
,(,), respectively, in the resulting graph G. In this paper, we show that the problem can be solved in polynomial time if r
k is given by r
k,(, ) = 2 for all , V. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-63890-3_12 | ISAAC |
Keywords | Field | DocType |
augmenting edge,vertex connectivities simultaneously,polynomial time | Integer,Discrete mathematics,Graph,Combinatorics,Multigraph,Vertex (geometry),Algorithm complexity,Vertex connectivity,Connectivity,Time complexity,Mathematics | Conference |
Volume | ISSN | ISBN |
1350 | 0302-9743 | 3-540-63890-3 |
Citations | PageRank | References |
6 | 0.52 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |