HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE
Department of Computer Science Seminar
On Decomposing a Multigraph into Triconnected Components
Dr. Yung H. Tsin
School of Computer Science
University of Windsor
Date: July 30, 2010 (Friday)
Time: 2:30 - 3:30 pm
Venue: SCT714, Cha Chi Ming Science Tower, Ho Sin Hang Campus
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.
********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)
Department of Computer Science, Hong Kong Baptist University