HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE

Department of Computer Science Seminar
2008 Series

Two New Linear-time Algorithms for 3-Edge-Connectivity

Dr. Yung H. Tsin
School of Computer Science
University of Windsor

Date: April 25, 2008 (Friday)
Time: 11:00 am - 12:00 pm
Venue: FSC1217, Fong Shu Chuen Library, Ho Sin Hang Campus

Abstract
The notion of 3-edge-connectivity, in addition to its traditional applications in network reliability, has applications in physics and quantum chemistry where the Feynman diagram is used. In computational biology, 3-edge-connectivity had recently been used in an FPT (Fixed-Parameter Tractable) algorithm for analyzing protein-protein networks obtained from microarray data. Two linear-time algorithms for 3-edge-connectivity are presented. The first one uses a new graph-transformation operation to gradually transform the input graph into an edgeless graph so that every vertex in it corresponds to a 3-edge-connected component of the input graph. The second one uses a stack to determine a set of cut-pairs based on a characterization theorem. Removing the cut-pairs leads to the 3-edge-connected components. In comparison with the previously best known algorithm, both algorithms make only one pass over the input graph and are conceptually simple and easy to implement. An experimental study involving the two algorithms and the previously best known algorithm had been performed. The experimental results show that the first algorithm has the best performance in determining the 3-edge-connected components while the second algorithm has the best performance in determining if the input graph is 3-edge-connected and in determining cut-pairs.

Biography
Yung H. Tsin received his B.Sc. degree from the Nanyang University (merged with the University of Singapore to form the National University of Singapore in 1980), his M.Sc. degree from the University of Calgary and his Ph.D. degree from the University of Alberta, respectively. He is currently an associate professor of the School of Computer Science at the University of Windsor. His current research interest is in the design and analysis of graph algorithms on different computer models, including the self-stabilizing model.

********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)

http://www.comp.hkbu.edu.hk/v1/?page=seminars&id=25
Photos