Engineering an External Memory Minimum Spanning Tree Algorithm

Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F.; Lévy, Jean-Jacques; Mayr, Ernst W.; Mitchell, John C.

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Engineering an External Memory Minimum Spanning Tree Algorithm

MPS-Authors

/persons/resource/persons44293

Dementiev, Roman
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45344

Sanders, Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45427

Schultes, Dominik
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Dementiev, R., Sanders, P., Schultes, D., & Sibeyn, J. F. (2004). Engineering an External Memory Minimum Spanning Tree Algorithm. In 3rd IFIP International Conference on Theoretical Computer Science (TSC2004) (pp. 195-208). Norwell, USA: Kluwer.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-292C-2

要旨

We develop an external memory algorithm for computing minimum spanning trees. The algorithm is considerably simpler than previously known external memory algorithms for this problem and needs a factor of at least four less I/Os for realistic inputs. Our implementation indicates that this algorithm processes graphs only limited by the disk capacity of most current machines in time no more than a factor 2--5 of a good internal algorithm with sufficient memory space.