A simple 3-edge connected component algorithm revisited

Graph connectivity is a graph-theoretic concept that is fundamental to the studies of many applications such as network reliability and network decomposition. For the 3-edge-connectivity problem, recently, it has been shown to be useful in a variety of apparently unrelated areas such as solving the G-irreducibility of Feynman diagram in physics and quantum chemistry, editing cluster and aligning genome in bioinformatics, placing monitors on the edges of a network in flow networks, spare capacity allocation and decomposing a social network to study its community structure. A number of linear-time algorithms for 3-edge-connectivity have thus been proposed. Of all these algorithms, the algorithm of Tsin is conceptually the simplest and also runs efficiently in a recent study. In this article, we shall show how to simplify the implementation of a key step in the algorithm making the algorithm much more easier to implement and run more efficiently. The simplification eliminates a rather complicated linked-lists structure and reduces the space requirement of that step from O(|E|) to O(|V|), where V and E are the vertex set and the edge set of the input graph, respectively.