Colloquia / Seminars / Industry Talks

The problem of decomposing a multigraph into triconencted components has applications in a variety of areas, such as analyzing electrical circuits, planar graph isomorphism and graph drawing. The best-known linear-time algorithm for the problem by Hopcroft and Tarjan contains quite a few errors that make it difficult to comprehend and implement correctly. Gutwenger and Mutzel presented a list of those errors and explained how to fix them. Unfortunately, their explanation was brief and incomplete. We shall present a new linear-time algorithm. The algorithm uses a new graph transformation technique to gradually transform the graph into a collection of split components from which the triconnected components are easily determined. The algorithm is conceptually simple. The new graph transformation technique may be useful in other context.

Yung H. Tsin received his B.Sc. degree in mathematics from Nanyang University, Singapore (merged with the University of Singapore in 1980 to form the current National University of Singapore), his M.Sc. degree in computer science from the University of Calgary at Calgary, Alberta, and his Ph.D. degree in computing science from the University of Alberta at Edmonton, Alberta. His is currently a faculty member of the School of Computer Science at the University of Windsor, Ontario, Canada. His current research interests include graph algorithms, parallel and distributed computing.