A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.5   pp.1263-1268
Publication Date: 2006/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.5.1263
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
algorithm,  connectivity augmentation,  edge-connectivity,  edge-splitting,  extreme vertex sets,  graph,  

Full Text: PDF(166.6KB)>>
Buy this Article

Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n2log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.