Loading...
Please wait, while we are loading the content...
Similar Documents
A Linear Time Algorithm for Tri-connectivity Augmentation of Bi-connected Graphs with Upper Bounds on Vertex-Degree Increase
| Content Provider | Semantic Scholar |
|---|---|
| Author | Mashima, Toshiya Taoka, Satoshi Watanabe, Toshimasa |
| Copyright Year | 2008 |
| Abstract | The 3-vertex-connectivity augmentation problem of a graph with degree constraints, 3VCA-DC, is defined as follows: “Given an undirected graph G = (V,E), and an upper bound b(v) ∈ Z+ ∪ {∞} on vertex-degree increase for each v ∈ V , find a smallest set E´ of edges such that (V,E∪E´) is 3-vertex-connected and such that vertex-degree increase of each v ∈ 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 3VCA-DC for any bi-connected graph G can be done in O(|V| + |E|) time. |
| Starting Page | 313 |
| Ending Page | 316 |
| Page Count | 4 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ieice.org/proceedings/ITC-CSCC2008/pdf/p313_F2-5.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
