A Simplified Õ(nm) Time Edge-Splitting Algorithm in Undirected Graphs

Abstract.

Let G=(V,E) be a multigraph which has a designated vertex s ∈ V with an even degree. For two edges e ₁ = (s,u ₁ ) and e ₂ = (s,u ₂ ) , we say that a multigraph G' is obtained from G by splitting e ₁ and e ₂ at s if two edges e ₁ and e ₂ are replaced with a single edge (u ₁ ,u ₂ ) . It is known that all edges incident to s can be split without losing the edge-connectivity of G in V-s . This complete splitting plays an important role in solving many graph connectivity problems. The currently fastest algorithm for a complete splitting [14] runs in O(n(m+n log n) log n) time, where n = |V| and m is the number of pairs of vertices between which G has an edge. Their algorithm is first designed for Eulerian multigraphs, and then extended for general multigraphs. Although the part for Eulerian multigraphs is simple, the rest for general multigraphs is considerably complicated.

This paper proposes a much simpler O(n(m+n log n) log n) time algorithm for finding a complete splitting. A new edge-splitting theorem derived from our algorithm is also presented.