At the invitation of Cuiying Honor College of Lanzhou University, Professor Xu Shoujun from School of Mathematics and Statistics came to our school to give a report. Teachers and students are welcome to participate.

Report topic: Search algorithm for graphs

Speaker: Professor Xu Shoujun

Report time: 19:00, September 22, 2021

Report location: A307, Second Teaching Building, Yuzhong Campus, Lanzhou University

Brief introduction of the speaker

Xu Shoujun, professor and doctoral supervisor of the School of Mathematics and Statistics, Lanzhou University. The main research direction is graph theory and its applications, discrete algorithms, approximate algorithms, algorithm complexity, etc. From 2008 to 2010, the Institute of Mathematics and Systems Science of the Chinese Academy of Sciences was engaged in postdoctoral work in the field of operations research; 2010.2-2011.2 and 2016.9-2017.9, the Department of Computer Science, University of California, Davis visited for two years; June 2013 to September 2015 From December 2015 to January 2016, the Hong Kong Institute of Education visited; currently at SIAM J Discrete Math., Inform. Process. Lett. Discrete Appl. Math, Theor. Comput. Sci., J. Combin. Optim., Australas. J . Published academic papers in journals such as Combin. Currently, he presides over one general project of the National Natural Science Foundation of China, and has presided over the completion of three projects of the National Natural Science Foundation of China.

Report summary

The search algorithm of graphs is widely used in real life. Many complex algorithms are actually the improvement and promotion of some basic algorithms. Starting from the most basic DFS algorithm and BFS algorithm, this article introduces Dijkstra algorithm, A* algorithm and Greedy in turn. Best First algorithms and their comparisons, to give everyone a preliminary understanding of their ideas and the relationship between these algorithms.

(Translated by He Yipeng, proofread by Bian Yujing and Li Shuowen)