Skip to content Skip to navigation

Academic Events

On Disjoint Shortest Paths

SPEAKER:Longlun Guo,Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University
WHEN: Wendesday, 2019, July 3-10:30

WHERE: Room 665,  Xingjian Building


Abstract: The classical disjoint shortest path problem has recently recalled interests from researchers in the networks planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partial disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the δ-vertex k edge-disjoint shortest path problem (δV-kEDSP), that is, for a pair of distinct vertices in a network graph, it optimally finds k edge-disjoint shortest paths between them where at most δ vertices are shared by at least two paths. We present techniques for exactly solving the problem with a time complexity significantly improving the runtime bound of the state-of-art. The proposed theoretical approaches are also validated by computer experiments on both synthetic and real networks which demonstrate their superior efficiency of up to three orders of magnitude faster than the state-of-art solution.
Bio: Jianli Chen received the B.Sc. degree in information and computing sciences, the M.Sc. degree in computer application technology, and the Ph.D. degree in applied mathematics, all from Fuzhou University, in 2007, 2009, and 2012, respectively. He is currently a distinguished professor with the Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University. His research interests include optimization theory and applications, and optimization methods for VLSI physical design automation. Dr. Chen received Best Paper Award from DAC 2017, Best Paper Award Nomination and Best-in-track Paper from ICCAD 2018, and Best-in-track Paper from ICCAD 2019. He and his group was the recipient of the First Place Award at the CAD Contest at ICCAD in 2017 and 2018, respectively. Dr. Chen also received the Distinguished Young Scholars Foundation of FuJian Province in 2018, and the CCF Integrated Circuit Early Career Award in 2018. He has served as a TPC for DAC, ICCAD, ASP-DAC, and so on. Since January 2018, he has served as a Design Automation Technical Committee of IEEE CEDA .

Bio: PhD supervisor and "qishan scholar" of Fuzhou University, director of the Department of Computer Science. In 2005 and 2011, he graduated from the University of Science and Technology of China with a bachelor's degree and a doctorate. His research interests include algorithm design and analysis related to parallel distributed computing and high-performance computer networks. He has published more than forty papers in international conferences including Algorithmica, IEEE TMC, IEEE TC, IEEE TPDS and other international conferences such as ACM Symposium on Parallelism in Algorithms and Architecture (SPAA) and IJCAI. Currently hosting a National Natural Science Fund, has hosted a national fund and a number of provincial and ministerial funds. He is currently a young director of the Mathematical Planning Society, a member of the Fujian Provincial Computer Society, and a member of the PDCAT, PAAP, and other high-performance computing and algorithm mainstream conference program committees (PC members)