Name
Abstract | ||
|---|---|---|
Given an undirected multigraph G = (V,E) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting multigraph becomes l-edge-connected and k-vertex-connected. In this paper, we show that the problem with a fixed l and k = 3 can be solved in polynomial time for an arbitrary multigraph G. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/3-540-49381-6_18 | ISAAC |
Keywords | Field | DocType |
3-vertex connectivity augmentation,new edge,edge-and-vertex connectivity augmentation problem,fixed l,polynomial time,positive integers l,undirected multigraph,arbitrary multigraph,resulting multigraph,smallest number | K-edge,Integer,Discrete mathematics,Combinatorics,Multigraph,Computational geometry,Combinatorial optimization,Vertex connectivity,Time complexity,Connectivity,Mathematics | Conference |
Volume | ISSN | ISBN |
1533 | 0302-9743 | 3-540-65385-6 |
Citations | PageRank | References |
4 | 0.43 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |