Abstract
The single-source shortest path (SSSP) problem is a fundamental problem in graph theory. In this talk we introduce a new deterministic algorithm for SSSP on real non-negative edge-weighted directed graphs, which runs in time . This improves the recent breakthrough result of time for directed SSSP algorithm [DMMSY25]. Our approach, inspired by a single-source bottleneck path (SSBP) algorithm [DLWX18], manages the frontier vertices more efficiently. This is a coauthored work with Prof. Ran Duan, Xinkai Shu and Xiao Mao
Time
Thursday, Mar.12, 10:00--11:00
Speaker
Longhui Yin is a fifth-year PhD student in Institute for Interdisciplinary Information Sciences (IIIS), advised by Prof. Andrew Chi-Chih Yao. His research focuses on combinatorical graph algorithms and data structure design problems
Room
Room 602
