Show simple item record

dc.contributor.authorChen, Zhangyun
dc.date.accessioned2014-03-03T20:01:16Z
dc.date.available2014-03-03T20:01:16Z
dc.date.issued2001-08
dc.identifier.otherchen_zhangyun_200108_ms
dc.identifier.urihttp://purl.galileo.usg.edu/uga_etd/chen_zhangyun_200108_ms
dc.identifier.urihttp://hdl.handle.net/10724/20201
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.publisheruga
dc.rightspublic
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.typeThesis
dc.description.degreeMS
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

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record