A new linear algorithm for checking a graph for 3-edge-connectivity
MetadataShow full item record
A new algorithm to test an arbitrary graph for 3-edge-connectivity is proposed, implemented and tested. It is a modi¯cation of the classic linear algorithm of Hopcroft and Tarjan for dividing a graph into 3-connected components. The algo- rithm uses three depth-¯rst 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.