Reducing edge connectivity to vertex connectivity

ABSTRACT

We show how to reduce edge connectivity to vertex connectivity. Using this reduction, we obtain a linear-time algorithm for deciding whether an undirected graph is 3-edge-connected, and for computing the 3-edge-connected components of an undirected graph.

REFERENCES

• 1: [1] J. Cheriyan, R. Thurimella, "On determining vertex connectivity", manuscript 1990.
• 2: [2] S. Even, "An algorithm for determining whether the the connectivity of a graph is at least k", SIAM J. Comput. 4 (1975), 393-396.
• 3: [3] S. Even, R. E. Tarjan, "Network flow and testing flow graph connectivity", SIAM J. Comput. 4 (1975), 507-518.
• 4: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
• 5: [5] Z. Galil, "Finding the vertex connectivity of graphs", SIAM J. Comput. 9 (1980), 197-199.
• 6: [6] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
• 7: [7] J. Hopcroft, R. E. Tarjan, "Dividing a graph into triconnected components", SIAM J. Comput. 2 (1973), 135-158.
• 8: [8] A. Kanevsky, V. Ramanchandran, "Improved algorithms for graph four-connectivity", Proc. 28th Annual Symp. on Foundations on Computer Science, 1987, 252-259.
• 9: [9] D. W. Matula, "Determining edge connectivity in O(nm)", Proc. 28th Annual Symp. on Foundations of Computer Science, 1987, 249-251.
• 10: Yishay Mansour , Baruch Schieber, Finding the edge connectivity of directed graphs, Journal of Algorithms, v.10 n.1, p.76-85, Mar. 1989 [doi>10.1016/0196-6774(89)90024-2]
• 11: [11] R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM J. Comput. 1 (1972), 146-160.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification