HKBU  |  SCI  |  BUniPort  |  Library  |  Alumni  |  Job Vacancies  |  Intranet  |  Sitemap        
Undergraduate Admissions
Taught Postgraduate Admissions
Research Postgraduate Admissions
News & Achievements
Research Highlights
Contact & Direction

Department of Computer Science Seminar
2010 Series

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)
Photos  Slides
Copyright © 2021. All rights reserved.Privacy Policy
Department of Computer Science, Hong Kong Baptist University
Hong Kong Baptist University