On four-connecting a triconnected graph
Author:
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 70-79
Abstract
The author considers the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks. He presents an O(n alpha (m,n)+m) time sequential algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and alpha (m, n) is the inverse Ackermann function. He presents a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. The new lower bound applies for arbitrary k, and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k-1)-connect graph. For k=4, he shows that this lower bound is tight by giving an efficient algorithm for finding a set edges with the required size whose addition four-connects a triconnected graph.Keywords
This publication has 20 references indexed in Scilit:
- Finding a Smallest Augmentation to Biconnect a GraphSIAM Journal on Computing, 1993
- On-line maintenance of the four-connected components of a graph1991
- A linear time augmenting algorithm for 3-edge-connectivity augmentation problems1991
- Augmentation problems on hierarchically defined graphsLecture Notes in Computer Science, 1989
- Fast parallel strong orientation of mixed graphs and related augmentation problemsJournal of Algorithms, 1988
- Minimum augmentation of a tree to a K‐edge‐connected graphNetworks, 1988
- Edge-connectivity augmentation problemsJournal of Computer and System Sciences, 1987
- The minimum augmentation of a directed tree to a k‐edge‐connected directed graphNetworks, 1986
- On Network AugmentationIEEE Transactions on Reliability, 1986
- The Design of Minimum-Cost Survivable NetworksIEEE Transactions on Circuit Theory, 1969