ISSN:
1432-0541
Keywords:
Key words. Undirected graph, Multigraph, Edge-connectivity, Edge splitting, Minimum cut, Polynomial algorithm, Deterministic algorithm.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Let G=(V,E) be a multigraph which has a designated vertex s ∈ 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 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004539910004
Permalink
