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

2026-03-12  10:00 - 11:00

Speaker

Longhui Yin, Institute for Interdisciplinary Information Sciences

Room

Room 602