Show simple item record

dc.contributor.authorChen, Zhangyun
dc.description.abstractA 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 2000.
dc.subjectEdge connectivity
dc.subject3-edge-connected graph
dc.subjectLinear algorithm
dc.subjectQuadratic algorithm
dc.titleA linear time algorithm for testing a graph for 3-edge-connectivity
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorRobert W. Robinson
dc.description.committeeRobert W. Robinson
dc.description.committeeThiab Taha
dc.description.committeeEileen T. Kraemer

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record