-
- Camil Demetrescu
- Università di Roma "La Sapienza", Rome, Italy
-
- Giuseppe F. Italiano
- Università di Roma "Tor Vergata", Rome, Italy
書誌事項
- 公開日
- 2004-11
- 権利情報
-
- https://www.acm.org/publications/policies/copyright_policy#Background
- DOI
-
- 10.1145/1039488.1039492
- 公開者
- Association for Computing Machinery (ACM)
この論文をさがす
説明
<jats:p> We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>2</jats:sup> log <jats:sup>3</jats:sup> <jats:italic>n</jats:italic> ) amortized time per update and unit worst-case time per distance query, where <jats:italic>n</jats:italic> is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice. </jats:p>
収録刊行物
-
- Journal of the ACM
-
Journal of the ACM 51 (6), 968-992, 2004-11
Association for Computing Machinery (ACM)