Decomposing a Multigraph into Split Components

Tsin, Y. H.

A linear-time algorithm for decomposing a graph into split components is presented. The algorithm uses a new graph transformation technique to gradually transform the given graph so that every split component in it is transformed into a subgraph with very simple structure which can be easily identified. Once the split components are determined, the triconnected components of the graph are easily determined. The algorithm is conceptually simple and makes one less pass over the input graph than the existing best known algorithm which could mean substantial saving in actual execution time. The new graph transformation technique may be useful in other context.

Cite as: Tsin, Y. H. (2012). Decomposing a Multigraph into Split Components. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 3-12

(from crpit.com) (local if available)