Zhangyun Chen

"A Linear Time Algorithm for Testing a Graph for 3-Edge-Connectivity"

Abstract:

A graph G = (V, E) is 3-edge-connected if and only if the subgraph (V, E - S) is connected for every set S of at most 2 edges. Two versions of an algorithm to test an arbitrary graph for 3-edge-connectivity due to Nagamochi and Ibaraki were implemented and tested. This required making some modifications to the algorithm as originally described and filling in many details. The two versions implemented are called simplified and accelerated. For a graph with n vertices and m edges the simplified algorithm takes time O(nm), whereas the accelerated algorithm runs in time O(n + m). The simplified algorithm is less complex to code, so the implied constant is smaller for it than for the accelerated algorithm. Testing was done on Feynman diagrams; irreducibility for a Feynman diagram of order n is exactly 3-edge-connectivity for a contracted graph which has n vertices and maximum degree at most 4, hence m ≤ 2n. No significant difference in speed between the two algorithms was found for n ≤ 150. For larger n, the accelerated algorithm gradually becomes faster than the simplified one, for example being 10 times faster for n just over 3000.