External Memory BFS on Undirected Graphs with Bounded Degree

Meyer, Ulrich

External Memory BFS on Undirected Graphs with Bounded Degree

Meyer, U. (2001). External Memory BFS on Undirected Graphs with Bounded Degree. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01) (pp. 87-88). New York, USA: ACM.

Item is 公開

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

基本情報

表示: 非表示:

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

資料種別: 会議論文

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Meyer, Ulrich¹, 著者

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

内容説明

表示:

非表示:

キーワード: -

要旨: We give the first external memory algorithm for breadth-first search (BFS) which achieves $o(n)$ I/Os on arbitrary undirected graphs with $n$ nodes and maximum node degree $d$. Let $M$ and $B>d$ denote the main memory size and block size, respectively. Using $\mathrm{Sort}(x)=\Theta(\frac{x}{B}\cdot \log_{M/B}\frac{x}{B})$, our algorithm needs ${\cal O}(\frac{n}{\gamma \cdot \log_d B} + \mathrm{Sort}(n \cdot B^\gamma))$ I/Os and ${\cal O}(n \cdot B^\gamma)$ external space for an arbitrary parameter $0 <\gamma \le 1/2$. The result carries over to BFS, depth-first search (DFS) and single source shortest paths (SSSP) on undirected planar graphs with arbitrary node degrees.

資料詳細

表示:

非表示:

言語: eng - English

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

出版の状態: 出版

ページ: -

出版情報: New York, USA : ACM

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 518104
その他: Local-ID: C1256428004B93B8-742279EFD100CB67C12569DD004F3A5B-Meyer2001a

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)

種別: 会議論文集

著者・編者:

所属:

出版社, 出版地: New York, USA : ACM

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 87 - 88 識別子（ISBN, ISSN, DOIなど）: ISBN: 0-89871-490-7

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1