A simple 3-edge connected component algorithm revisited

作者：Norouzi Nima; Tsin Yung H^*

来源：Information Processing Letters, 2014, 114(1-2): 50-55.

DOI：10.1016/j.ipl.2013.09.010

• 3-edge-connectivity
• 3-edge-connected components
• Graph algorithms

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 0 (vertical bar E vertical bar) to O(vertical bar V vertical bar), where V and E are the vertex set and the edge set of the input graph, respectively.

• 出版日期2014-2