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
AbstractThe 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.
BiographyYung 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&lang=tc