Perfect Graphs and Their Applications in Brief

Date of Presentation: 
Wednesday, July 16, 2014
Faculty Sponsor: 
Senjuti Basu Roy
Quarter: 
2014 Summer
Research Focus: 

Speaker: Dr. Rajat Kumar Pal 
Title: Perfect Graphs and Their Applications in Brief

Abstract: Most of the applications of graph theory acquire modeling of some problem where computation of some graph theoretic invariant(s) provides desired solution(s) to the problem under consideration, and most of these invariants are intractable for a simple, symmetric, general graph.For example, different types  of perfect graph find a huge prospect in solving various real-life and scientific problems. As we are interested in the affluent algorithmic properties of various classes of perfect  graph, we initially focus on two types of classical perfect graphs, namely triangulated and comparability graph.

Gradually, we derive several subclasses of these two types of perfect graph by using some perfect preserving operations, and try to show some applications of them. Among many other types of perfect graph, split, interval, co-triangulated, co-comparability, permutation, weakly triangulated, threshold graph, etc. are only a few to mention that draw purely graph theoretic as well as research or other applications in our everyday life. One of the real-life examples focuses on advertising of various products through different programmes broadcasted on a range of television channels. Here the objective may be to compute a sequence of nonoverlapping programme slots that may help interested advertising agencies to give advertisement of their products and promote their messages to a maximum number of viewers of different predilections.

Bio: Dr. Rajat Kumar Pal received his B.E. in Electrical Engineering in 1985 from Bengal Engineering College, Shibpur, University of Calcutta, his M.Tech. in Computer Science and Engineering in 1988 from the University of Calcutta, and PhD in Computer Science and Engineering in 1996 from Indian Institute of Technology (I.I.T.), Kharagpur. Since 1994, he is serving the University of Calcutta as a faculty of the Department of Computer Science and Engineering. He worked as the Head of the Department of Computer Science and Engineering of this University for two years (April 2005 to April 2007). Later on, he became Professor of the Department of Information Technology of the Assam University at Silchar, a Central University (April 2010 to April 2012). He also acted as the Dean of the Triguna Sen School of Technology of Assam University (January 2011 to March 2012). At present, Dr. Pal is working as the Associate Professor of the Department of Computer Science and Engineering of the University of Calcutta.

His major research interests include VLSI design, Graph theory and its applications, Perfect graphs, Logic synthesis, Design and analysis of algorithms, Computational geometry, Parallel computation and algorithms. Dr. Pal has published more than 140 technical research articles, and authored and co-authored two books of international standard.