日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
 
 
ダウンロード電子メール
  Directed single-source shortest-paths in linear average-case time

Meyer, U.(2001). Directed single-source shortest-paths in linear average-case time (MPI-I-2001-1-002). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

基本情報

表示: 非表示:
資料種別: 報告書

ファイル

表示: ファイル
非表示: ファイル
:
2001-1-002 (全文テキスト(全般)), 11KB
ファイルのパーマリンク:
https://hdl.handle.net/11858/00-001M-0000-0014-6D46-1
ファイル名:
2001-1-002
説明:
-
OA-Status:
閲覧制限:
公開
MIMEタイプ / チェックサム:
text/html / [MD5]
技術的なメタデータ:
著作権日付:
-
著作権情報:
-
CCライセンス:
-

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Meyer, Ulrich1, 著者           
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

内容説明

表示:
非表示:
キーワード: -
 要旨: The quest for a linear-time single-source shortest-path (SSSP) algorithm on directed graphs with positive edge weights is an ongoing hot research topic. While Thorup recently found an ${\cal O}(n+m)$ time RAM algorithm for undirected graphs with $n$ nodes, $m$ edges and integer edge weights in $\{0,\ldots, 2^w-1\}$ where $w$ denotes the word length, the currently best time bound for directed sparse graphs on a RAM is ${\cal O}(n+m \cdot \log\log n)$. In the present paper we study the average-case complexity of SSSP. We give simple label-setting and label-correcting algorithms for arbitrary directed graphs with random real edge weights uniformly distributed in $\left[0,1\right]$ and show that they need linear time ${\cal O}(n+m)$ with high probability. A variant of the label-correcting approach also supports parallelization. Furthermore, we propose a general method to construct graphs with random edge weights which incur large non-linear expected running times on many traditional shortest-path algorithms.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2001
 出版の状態: 出版
 ページ: 32 p.
 出版情報: Saarbrücken : Max-Planck-Institut für Informatik
 目次: -
 査読: -
 識別子(DOI, ISBNなど): URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2001-1-002
Reportnr.: MPI-I-2001-1-002
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Research Report / Max-Planck-Institut für Informatik
種別: 連載記事
 著者・編者:
所属:
出版社, 出版地: -
ページ: - 巻号: - 通巻号: - 開始・終了ページ: - 識別子(ISBN, ISSN, DOIなど): -