Paper Info
Title
Simultaneous Augmentation of Two Graphs to an l-Edge-Connected Graph and a Biconnected Graph
Abstract
Given two undirected multigraphs G = (V, E) and H = (V, K), and two nonnegative integers l and k, we consider the problem of augmenting G and H by a smallest edge set F to obtain an l-edge-connected multigraph G + F = (V, E ∪ F) and a k-vertex-connected multigraph H + F = (V, K ∪ F). The problem includes several augmentation problems that require to increase the edge- and vertex-connectivities simultaneously. In this paper, we show that the problem with l ≥ 2 and k = 2 can be solved by adding at most one edge over the optimum in O(n4) time for two arbitrary multigraphs G and H, where n = |V|. In particular, we show that if l is even, then the problem can be solved optimally.
Year
DOI
Venue
2000
10.1007/3-540-40996-3_28
ISAAC
Keywords
Field
DocType
k-vertex-connected multigraph h,smallest edge set f,biconnected graph,simultaneous augmentation,arbitrary multigraphs g,l-edge-connected multigraph,nonnegative integers l,l-edge-connected graph,augmenting g,undirected multigraphs g,augmentation problem,connected graph
Integer,Data structure,Graph,Discrete mathematics,Combinatorics,Multigraph,Biconnected graph,Combinatorial optimization,Graph rewriting,Connectivity,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-41255-7
0
0.34
References 
Authors
10
2
Name
Order
Citations
PageRank
Toshimasa Ishii111017.03
Hiroshi Nagamochi21513174.40