應(yīng)yl7703永利官網(wǎng)徐守軍教授邀請，香港理工大學(xué)計(jì)算機(jī)系助理教授、中南大學(xué)教授操宜新將于2019年8月2-5日訪問我校并作學(xué)術(shù)報(bào)告。

報(bào) 告1：Interval graphs and (normal Helly) circular-arc graphs

時 間：08月03日下午15:00

地 點(diǎn)：齊云樓911報(bào)告廳

摘要：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.

報(bào) 告2：Enumerating Maximal Induced Subgraphs

時 間：08月04日上午08:30

地 點(diǎn)：齊云樓911報(bào)告廳
摘要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.
    歡迎廣大師生參加！

報(bào)告人簡介

操宜新博士是香港理工大學(xué)計(jì)算機(jī)系助理教授、中南大學(xué)教授（博導(dǎo)），于2012在美國德州農(nóng)機(jī)大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位。操博士具備相關(guān)業(yè)界經(jīng)驗(yàn)，在其獲得博士學(xué)位前，他曾任程序設(shè)計(jì)員達(dá)五年?；貒?，他在匈牙利科學(xué)院計(jì)算機(jī)科學(xué)與控制研究所做研究員。曾任布朗大學(xué)計(jì)算與實(shí)驗(yàn)研究所（ICRM）、卑爾根大學(xué)信息學(xué)系訪問學(xué)者。操宜新博士的研究興趣是算法圖論，細(xì)粒度復(fù)雜性和算法設(shè)計(jì)，組合優(yōu)化，以及它們在生物信息學(xué)和社會網(wǎng)絡(luò)中的應(yīng)用。他的研究得到了香港研究資助委員會（RGC）和國家自然科學(xué)基金（NSFC）的支持。

甘肅省應(yīng)用數(shù)學(xué)與復(fù)雜系統(tǒng)省級重點(diǎn)實(shí)驗(yàn)室

yl7703永利官網(wǎng)

萃英學(xué)院

2019年7月31日