Document Type
Technical Report
Publication Date
2009
DOI:
10.7936/K7B856CD
Technical Report Number
wucse-2009-6
Abstract
Vertex-connectivity and edge-connectivity represent the extent to which a graph is connected. Study of these key properties of graphs plays an important role in varieties of computer science applications. Recent years have witnessed a number of linear time 3-edge-connectivity algorithms - with increasing simplicity. In contrast, the state-of-the-art algorithm for 3-vertex-connectivity due to Hopcroft and Tarjan lacks the simplicity in the sense of ease of implementation as well as the number of passes over the graph although its time and space complexity is theoretically linear. In this paper, we propose a linear time reduction from 3-vertex-connectivity to 3-edge- connectivity of a multigraph. This reduction was previously unknown, while the reduction in the opposite direction already exists. We apply an existing linear time 3-edge-connectivity algorithm on the reduced graph for solving the 3-vertex-connectivity of the original graph. Hence, for a graph with V vertices and E edges, the proposed reduction turns into an O(|V | +|E|) time and space algorithm for 3-vertex-connectivity while enjoying the simplicity of the 3-edge-connectivity algorithms.
Recommended Citation
Saifullah, Abusayeed and Ungor, Alper, "A Simple Algorithm For Triconnectivity of a Multigraph" Report Number: wucse-2009-6 (2009). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/20
Comments
Permanent URL: http://dx.doi.org/10.7936/K7B856CD