Name
Title | ||
|---|---|---|
Augmenting a (kappa-1)-Vertex-Connected Multigraph to an iota-Edge-Connected and kappa-Vertex-Connected Multigraph |
Abstract | ||
|---|---|---|
Given an undirected multigraph G = (V,E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected multigraph. In this paper, we show that an (k - 1)-vertex-connected multigraph G (k 驴 4) can be made l-edge-connected and k-vertex-connected by adding at most 2l surplus edges over the optimum, in O(min{k,驴n}kn3 + n4) time, where n = |V|. |
Year | Venue | Keywords |
|---|---|---|
1999 | ESA | new edge,surplus edge,vertex-connected multigraph,positive integers l,undirected multigraph,augmenting g,smallest number,k-vertex-connected multigraph,kappa-vertex-connected multigraph |
Field | DocType | ISBN |
Integer,Discrete mathematics,Kappa,Combinatorics,Multigraph,Vertex (geometry),Iota,Mathematics | Conference | 3-540-66251-0 |
Citations | PageRank | References |
3 | 0.42 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |