DagSemProc.04301.2.pdf
- Filesize: 172 kB
- 2 pages
Document
A Simple Algorithm for I/O-efficiently Pruning Dense Spanners
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 4301
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
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.
Keywords
- No keywords
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads