Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Given a geometric graph G=(S,E) in Rd 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|)) memory transfers in the cache-oblivious model of computation. The main building block of our algorithm, and of independent interest in itself, is a new cache-oblivious algorithm for constructing a well-separated pair decomposition which builds such a data structure for a given point set S⊂Rd using O(sort(|S|)) memory transfers.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Journal of Discrete Algorithms |
Vol/bind | 8 |
Udgave nummer | 3 |
Sider (fra-til) | 259-272 |
Antal sider | 14 |
ISSN | 1570-8667 |
DOI | |
Status | Udgivet - 2010 |
Eksternt udgivet | Ja |
ID: 167918709