$\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm

Meyer, Ulrich; Sanders, Peter

$\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm

Meyer, U., & Sanders, P. (1998). $\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm. In G., Bilardi, G. F., Italiano, A., Pietracaprina, & G., Pucci (Eds.), Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98) (pp. 393-404). Berlin, Germany: Springer.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-377B-C 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-377D-8

資料種別: 会議論文

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Meyer, Ulrich¹, 著者
Sanders, Peter¹, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: In spite of intensive research, little progress has been made towards fast and work-efficient parallel algorithms for the single source shortest path problem. Our \emph{$\Delta$-stepping algorithm}, a generalization of Dial's algorithm and the Bellman-Ford algorithm, improves this situation at least in the following ``average-case'' sense: For random directed graphs with edge probability $\frac{d}{n}$ and uniformly distributed edge weights a PRAM version works in expected time ${\cal O}(\log^3 n/\log\log n)$ using linear work. The algorithm also allows for efficient adaptation to distributed memory machines. Implementations show that our approach works on real machines. As a side effect, we get a simple linear time sequential algorithm for a large class of not necessarily random directed graphs with random edge weights.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2010-03-02出版: 1998

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 517932
その他: Local-ID: C1256428004B93B8-460E70E77293F8C7C1256678004E0EF2-MeyerSanders1998a

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)

種別: 会議論文集

著者・編者:
Bilardi, Gianfranco, 編集者
Italiano, Giuseppe F., 編集者
Pietracaprina, Andrea, 編集者
Pucci, Geppino, 編集者

所属:
-

出版社, 出版地: Berlin, Germany : Springer

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 393 - 404 識別子（ISBN, ISSN, DOIなど）: ISBN: 3-540-64848-8

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Computer Science

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: 1461 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2