Implementation of O(nmlog n) Weighted Matchings: The Power of Data Structures

Mehlhorn, Kurt; Schäfer, Guido

doi:10.1007/3-540-44691-5_3

Implementation of O(nmlog n) Weighted Matchings: The Power of Data Structures

Mehlhorn, K., & Schäfer, G. (2000). Implementation of O(nmlog n) Weighted Matchings: The Power of Data Structures. In S., Näher, & D., Wagner (Eds.), Algorithm Engineering (pp. 23-38). Berlin: Springer. doi:10.1007/3-540-44691-5_3.

Item is 公開

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

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-335D-E 版のパーマリンク: https://hdl.handle.net/21.11116/0000-000E-4562-6

資料種別: 会議論文

LaTeX : Implementation of $O(nm \log n)$ weighted matchings: The power of data structures

ファイル

表示: ファイル

非表示: ファイル

:

154.pdf (全文テキスト（全般）), 279KB

ファイルのパーマリンク:
-

ファイル名:
154.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Mehlhorn, Kurt¹, 著者
Schäfer, Guido¹, 著者

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

内容説明

表示:

非表示:

キーワード: -

要旨: We describe the implementation of an $O(nm \log n)$ algorithm
for weighted matchings in general graphs. The algorithm is a variant of the
algorithm of Galil, Micali, and Gabow and requires the use of concatenable
priority queues. No previous implementation had a worst-case guarantee of
$O(nm \log n)$. We compare our implementation to the experimentally fastest
implementation (called Blossom IV) due to Cook and Rohe; Blossom IV is an
implementation of Edmonds' algorithm and has a running time no better than
$O(n^3)$. Blossom IV requires only very simple data structures.
Our experiments show that our new implementation is competitive
to Blossom IV.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2006-06-20オンライン出版: 2000出版: 2000

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 344453
BibTex参照ID: Mehlhorn-Schaefer:WeightedMatchings
DOI: 10.1007/3-540-44691-5_3

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Algorithm Engineering

副タイトル : 4th International Workshop, WAE 2000 ; Saarbr ̈ucken, Germany, September 5-8, 2000 ; Proceedings

省略形 : WAE 2000

種別: 会議論文集

著者・編者:
Näher, Stefan¹, 編集者
Wagner, Dorothea¹, 編集者

所属:
1 External Organizations, ou_persistent22

出版社, 出版地: Berlin : Springer

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

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Computer Science

省略形 : LNCS

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

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

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2