A Simplified Õ(nm) Time Edge-Splitting Algorithm in Undirected Graphs |
| |
Authors: | H Nagamochi S Nakamura T Ibaraki |
| |
Affiliation: | (1) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan 606-8501. ibaraki@kuamp.kyoto-u.ac.jp, naga@kuamp.kyoto-u.ac.jp., JP |
| |
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.
Received March 13, 1997; revised October 10, 1997. |
| |
Keywords: | , Undirected graph, Multigraph, Edge-connectivity, Edge splitting, Minimum cut, Polynomial algorithm, Deterministic,,,,,algorithm, |
本文献已被 SpringerLink 等数据库收录! |
|