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

onghui Yin

Room

Room 602