Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874283 | Information Processing Letters | 2014 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nima Norouzi, Yung H. Tsin,