Seminar: The Most Frequent Connected Induced Subgraph

Speaker

Dr. Srinibas Swain, PhD

Assistant Professor at the Indian Institute of Information Technology, Guwahati

Abstract

The frequency of an unlabeled graph H in a graph G is the number of induced subgraphs of G that are isomorphic to H. The graph H is a most frequent connected induced subgraph (MFCIS) of G if the frequency of H in G is maximum among all unlabeled graphs occurring as induced subgraphs of G. We introduce the MFCIS problem and discuss some results on it including its complexity. We found by computation that the MFCIS of all non-clique graphs of up to 12 vertices is always one of the following graphs: $K2, K3, P2, P3$, where $Pk$ denotes the path graph with k edges. All these graphs are of order at most 4, however we give an infinite class of graphs whose MFCIS contains 60% of the vertices of the graph. We also determine MFCIS of some special classes of graphs.

Bio

Srinibas is an assistant professor in the CSE Department of IIIT Guwahati. He completed his MS in CSE from IIT Madras and PhD from Monash University at Melbourne. His research focus is in Theoretical Computer Science and Discrete Mathematics. After completing his MS, he worked for Oracle India Pvt. Ltd, Bangalore as a member of technical staff for 3.5 years. 

Meeting details will be emailed to the faculty and students.

Visit the CS Seminars Page for more information about Computer Science Seminars