Logo der Universität Wien

Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs

Abstract

We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an \tilde O(mn^{0.984}) expected total update time for SSSR and (1+?)-approximate SSSP, where \tilde O(

Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna