On shredders and vertex connectivity augmentation |
| |
Authors: | Gilad Liberman Zeev Nutov |
| |
Affiliation: | aThe Open University of Israel, Department of Computer Science, 108 Ravutski Str., POB 808, Raanana 43107, Israel |
| |
Abstract: | We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight. |
| |
Keywords: | Node-connectivity augmentation Shredders Exact/approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |