I/OEfficiently Pruning Dense Spanners

American Medical Informatics Association 2009 Annual Symposium

Joachim Gudmundsson1 ; Jan Vahrenhold2 ; 2 Westfa¨lische Wilhelms-Universita¨t Mu¨nster ; Institut fu¨r Informatik ; 48149 Mu¨nster ; Germany.

PID  :  77046

来源: CEUR

【 摘 要 】

Given a geometric graph G = (S,E) in Rdwith constant dilation t, and a positive constant , we show how to construct a (1 + )spanner of G with O(|S|) edges