Summary
International Technical Conference on Circuits/Systems, Computers and Communications
2008
Session Number:F2
Session:
Number:F2-5
A Linear Time Algorithm for Tri-connectivity Augmentation of Bi-connected Graphs with Upper Bounds on Vertex-Degree Increase
Toshiya Mashima, Satoshi Taoka, Toshimasa Watanabe,
pp.-
Publication Date:2008/7/7
Online ISSN:2188-5079
Summary:
The $3$-vertex-connectivity augmentation problem of a graph with degree constraints, $3$VCA-DC, is defined as follows: ``Given an undirected graph $G=(V,E)$, and an upper bound $b(v)\in Z^+\cup\{\infty\}$ on vertex-degree increase for each $v\in V$, find a smallest set $E'$ of edges such that $(V,E\cup E')$ is 3-vertex-connected and such that vertex-degree increase of each $v\in V$ by the addition of $E'$ to $G$ is at most $b(v)$, where $Z^+$ is the set of nonnegative integers.''In this paper we show that checking the existence of a feasible solution and finding an optimum solution to $3$VCA-DC for any bi-connected graph $G$ can be done in $O(|V|+|E|)$ time.