Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2009

Filename

wucse-2009-6.pdf

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7B856CD

Download

Share

COinS