I/O-Efficiently Pruning Dense Spanners

Cache-Oblivious and Cache-Aware Algorithms

计算机科学;物理学

Joachim Gudmundsson ; Jan Vahrenhold ; Institut fu¨r Informatik ; 48149 Mu¨nster ; Germany.

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/156/pdf/04301.VahrenholdJan.ExtAbstract.156.pdf
PID  :  7296

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Given a geometric graph G = (S,E) in R~d with constant dilation t, and a positive constant ε, we show how to construct a (1 + ε)-spanner of G with O(|S|) edges using O(sort(|E|)) I/Os.