Path Based Development Of Connectivity Algorithms

Abstract

This paper presents notions of 1- and 2-connectivity. It starts with 1-connectivity of directed graphs, and it then examines 2-connectivity of undirected graphs. Depth-first search is the method of choice to calculate low order connectivity information.  The algorithms which are designed for connectivity properties are originally due to Tarjan [1]. This paper follows the path-based development of [2], which simplifies the algorithms to eliminate the depth-first spanning tree.