应数学与统计学院徐守军教授邀请，香港理工大学计算机系助理教授、中南大学教授操宜新将于2019年8月2-5日访问我校并作学术报告。
报 告1：Interval graphs and (normal Helly) circular-arc graphs
时 间：08月03日下午15:00
地 点：齐云楼911报告厅
摘要：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.
报 告2：Enumerating Maximal Induced Subgraphs
时 间：08月04日上午08:30
地 点：齐云楼911报告厅
摘要2：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.
欢迎广大师生参加！
报告人简介
操宜新博士是香港理工大学计算机系助理教授、中南大学教授（博导），于2012在美国德州农机大学获得计算机科学博士学位。操博士具备相关业界经验，在其获得博士学位前，他曾任程序设计员达五年。回国前，他在匈牙利科学院计算机科学与控制研究所做研究员。曾任布朗大学计算与实验研究所（ICRM）、卑尔根大学信息学系访问学者。操宜新博士的研究兴趣是算法图论，细粒度复杂性和算法设计，组合优化，以及它们在生物信息学和社会网络中的应用。他的研究得到了香港研究资助委员会（RGC）和国家自然科学基金（NSFC）的支持。
甘肃省应用数学与复杂系统省级重点实验室
数学与统计学院
萃英学院
2019年7月31日
