Feng Sun

"A New Linear Algorithm for Checking a Graph for 3-Edge-Connectivity"

A new algorithm to test an arbitrary graph for 3-edge-connectivity is proposed, implemented and tested. It is a modification of the classic linear algorithm of Hopcroft and Tarjan for dividing a graph into 3-connected components. The algorithm uses three depth-first searches to locate separation pairs. It runs in time O(m+n), where m is the number of edges and n is the number of vertices in the graph. Testing was done on simple graphs and Feynman diagrams. The results show good agreement with the time complexity analysis, validating the algorithm design and implementation.