Deterministic (O)over-tilde(nm) time edge-splitting in undirected graphs

This paper presents a deterministic O(nm log n + n(2) log(2) n) = (O) over tilde(nm) time algorithm for splitting off all edges incident to a vertex s of even degree in a multigraph G, where n and m are the numbers of vertices and links (= vertex pairs between which G has an edge) in G, respectively. Based on this, many graph algorithms using edge-splitting can run faster. For example, the edge-connectivity augmentation problem in an undirected multigraph can be solved in (O) over tilde(nm) time, which is an improvement over the previously known randomized (O) over tilde(n(3)) bound and deterministic (O) over tilde(n(2)m) bound.