應(yīng)yl7703永利官網(wǎng)徐守軍教授邀請(qǐng)，重慶理工大學(xué)理學(xué)院李鵬副教授將于2019年7月23日至8月3日訪問我校并作系列學(xué)術(shù)報(bào)告。

報(bào) 告1：The maximum internal spanning tree problem of interval graphs

時(shí) 間：07月25日下午15:00

地 點(diǎn)：齊云樓815教室

摘要1：In this lecture, we introduce the maximum internal spanning tree problem. Using the nice properties of the normal orderings and the Hamiltonian thickness of interval graphs, we get a linear time algorithm to solve the maximum internal spanning tree problem of interval graphs.

報(bào) 告2：Some graph search algorithms

時(shí) 間：07月26日上午09:30

地 點(diǎn)：榆中校區(qū) 天山堂A314教室

摘要2：We study several graph search algorithms, including Lexicographic Breadth-First Search (LBFS), Maximum Cardinality Search (MCS), and Maximal Neighborhood Search (MNS). We develop the MNS properties of rigid interval graphs and characterize this graph class in several different ways. This allows us to obtain several linear time multi-sweep MNS algorithms for recognizing rigid interval graphs and unit interval graphs, as well as generalizing a corresponding 3-sweep LBFS algorithm for unit interval graph recognition designed by Corneil in 2004. For unit interval graphs, we even present a new linear time 2-sweep MNS certifying recognition algorithm.

報(bào) 告3：Spanning connectedness and Hamiltonian thickness of graphs(1)

時(shí) 間：07月30日下午15:00

地 點(diǎn)：齊云樓815教室

報(bào) 告4：Spanning connectedness and Hamiltonian thickness of graphs(2)

時(shí) 間：07月31日下午15:00

地 點(diǎn)：齊云樓815教室

摘要：A spanning connectedness property is one which involves the robust existence of a spanning subgraph which is of some special form, say a Hamiltonian cycle in which a sequence of vertices appear in an arbitrarily given ordering, or a Hamiltonian path in the subgraph obtained by deleting any three vertices and so on. Our main discovery is that the existence of a thick Hamiltonian vertex ordering will guarantee that the graph has various kinds of spanning connectedness properties and that for interval graphs, quite a few seemingly unrelated spanning connectedness properties are equivalent to the existence of a thick Hamiltonian vertex ordering. Due to the close connection between Hamiltonian thickness and spanning connectedness properties, we present several linear time algorithms for associated problems.

歡迎廣大師生參加！

報(bào)告人簡(jiǎn)介

李鵬，重慶理工大學(xué)理學(xué)院副教授，于2014年在上海交通大學(xué)獲得博士學(xué)位。2017年獲得國(guó)家青年基金，主要從事圖搜索算法方面的研究，包括區(qū)間圖、賦權(quán)區(qū)間圖、路覆蓋的算法等。

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

yl7703永利官網(wǎng)

萃英學(xué)院

2019年7月25日