A Simple Algorithm for I/O-efficiently Pruning Dense Spanners
AuthorsJoachim Gudmundsson,Jan Vahrenhold
- Part of: Volume:Dagstuhl Seminar Proceedings, Volume 4301
Part of: Series:Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license - Publication Date: 2005-07-01
Cite AsGet BibTex
Joachim Gudmundsson and Jan Vahrenhold. A Simple Algorithm for I/O-efficiently Pruning Dense Spanners. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)https://doi.org/10.4230/DagSemProc.04301.2
Abstract
Given a geometric graph $G=(S,E)$ in $R^d$ with constant dilation $t$, and a positive constant $\epsilon$, we show how to construct a $(1+\epsilon)$-spanner of $G$ with $O(|S|)$ edges using $O(sort(|E|))$ I/O operations.
Subject Classification
Keywords
- No keywords
Metrics
- Access Statistics
- Total Accesses (updated on a weekly basis)0PDF Downloads0Metadata Views