Name
Title | ||
|---|---|---|
Multigraph augmentation under biconnectivity and general edge-connectivity requirements |
Abstract | ||
|---|---|---|
Given an undirected multigraph G =(V, E) and a requirement function r(lambda): ((V)(2)) --> Z(+) (where ((V)(2)) is the set of all pairs of vertices and Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair x, y is an element of V become at least r(lambda) (x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n(3)(m + n) log(n(2)/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n? log n) log n), in the case of the uniform requirement r lambda (x, y) = l for all x, y is an element of V. Furthermore, for the general r(lambda), we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed l* = max{r lambda (x, y) \ x, y is an element of V}. (C) 2001 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1002/net.4 | NETWORKS |
Keywords | Field | DocType |
undirected multigraph,edge-connectivity,vertex-connectivity,graph augmentation,polynomial deterministic algorithm | Integer,Discrete mathematics,Binary logarithm,Combinatorics,Multigraph,Vertex (geometry),Upper and lower bounds,Connectivity,Time complexity,Deterministic system (philosophy),Mathematics | Journal |
Volume | Issue | ISSN |
37 | 3 | 0028-3045 |
Citations | PageRank | References |
1 | 0.36 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |