Invited by Prof. Shoujun Xu from School of Mathematics and Statistics, Dr. Yixin Cao, assistant professor from Hong Kong Polytechnic University & professor from Central South University, will visit our school and give a series of lectures from August 2nd to August 5th in 2019.

Title 1：Interval graphs and (normal Helly) circular-arc graphs

Time：3:00 p.m. August 3rd, 2019

Venue：Room 911, Qiyun Building

Abstract：Interval graphs are arguably the simplest and most useful graph class. Circular-arc graphs, whose characterization by forbidden induced subgraphs has been a notorious open problem for more than half century, are the most complicated. We focus on a special subclass of circular-arc graphs, namely normal Helly circular-arc graphs, and build a novel connection between it and interval graphs. We show several combinatorial and algorithmic applications of this connection.

Title 2：Enumerating Maximal Induced Subgraphs

Time：8:30 a.m. August 4th, 2019

Venue：Room 911, Qiyun Building

Abstract：We study efficient algorithms for the maximal induced subgraphs problem: Given a graph on vertices, enumerate all its maximal induced subgraphs that belong to a particular hereditary graph class. While its optimization version, known as the vertex deletion problem in literature, has been intensively studied, algorithms for the enumeration version exist only for few simple graph classes, e.g., independent sets and cliques. We first show that the maximal induced subgraphs problem can be solved in polynomial total time if and only if it can be solved in incremental polynomial time. We then propose general approaches to develop polynomial-delay algorithms and incremental-polynomial-time algorithms for the problem. They enable us to develop simple algorithms to solve the problem with polynomial delay for a large number of graph classes, and in incremental polynomial time for interval graphs, chordal graphs as well as two of its well-studied subclasses, and all graph classes with finite forbidden induced subgraphs.

Curriculum Vitae

Dr. Yixin Cao is a research assistant professor at Department of Computing from Hong Kong Polytechnic University, as well as a professor at School of Mathematics and Statistics from Central South University. He received the B.E. degree in automation from Harbin Engineering University, China in 2000, the M.Sc. degree in computer science from Beihang University, China in 2003, and Ph.D. degree in computer science from Texas A&M University, USA in 2012.

Before taking the current position, Dr. Cao was a research fellow at Institute for Computer Science and Control, Hungarian Academy of Sciences. He has been visiting scholar in Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University. His general research interests are in graph algorithms, combinatorial optimization, and their usages in social networks.

Welcome to attend!

Provincial Key Laboratory of Applied Mathematics and Complex Systems,

Gansu Province

School of mathematics and statistics

CuiyingHonors College

July 31st, 2019