应数学与统计学院徐守军教授邀请，重庆理工大学理学院李鹏副教授将于2019年7月23日至8月3日访问我校并作系列学术报告。

报 告1：The maximum internal spanning tree problem of interval graphs

时 间：07月25日下午15:00

地 点：齐云楼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.

报 告2：Some graph search algorithms

时 间：07月26日上午09:30

地 点：榆中校区 天山堂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.

报 告3：Spanning connectedness and Hamiltonian thickness of graphs(1)

时 间：07月30日下午15:00

地 点：齐云楼815教室

报 告4：Spanning connectedness and Hamiltonian thickness of graphs(2)

时 间：07月31日下午15:00

地 点：齐云楼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.

欢迎广大师生参加！

报告人简介

李鹏，重庆理工大学理学院副教授，于2014年在上海交通大学获得博士学位。2017年获得国家青年基金，主要从事图搜索算法方面的研究，包括区间图、赋权区间图、路覆盖的算法等。

甘肃省应用数学与复杂系统省级重点实验室

数学与统计学院

萃英学院

2019年7月25日