A simplified (O)over-tilde(nm) time edge-splitting algorithm in undirectedgraphs

Let G = (V, E) be a multigraph which has a designated vertex s is an elemen t of V with an even degree. For two edges e(1) = (s, u(1)) and e(2) = (s, u (2)), we say that a multigraph G' is obtained from G by splitting e(1) and e(2) at s if two edges e(1) and e(2) are replaced with a single edge (u(1), u(2)). It is known that all edges incident to s can be split without losin g the edge-connectivity of G in V - s. This complete splitting plays an imp ortant role in solving many graph connectivity problems. The currently fast est 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 com plicated. 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 fro m our algorithm is also presented.