Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies. / Gieseke, Fabian; Gudmundsson, Joachim; Vahrenhold, Jan.

In: Journal of Discrete Algorithms, Vol. 8, No. 3, 2010, p. 259-272.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Gieseke, F, Gudmundsson, J & Vahrenhold, J 2010, 'Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies', Journal of Discrete Algorithms, vol. 8, no. 3, pp. 259-272. https://doi.org/10.1016/j.jda.2010.03.001

APA

Gieseke, F., Gudmundsson, J., & Vahrenhold, J. (2010). Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies. Journal of Discrete Algorithms, 8(3), 259-272. https://doi.org/10.1016/j.jda.2010.03.001

Vancouver

Gieseke F, Gudmundsson J, Vahrenhold J. Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies. Journal of Discrete Algorithms. 2010;8(3):259-272. https://doi.org/10.1016/j.jda.2010.03.001

Author

Gieseke, Fabian ; Gudmundsson, Joachim ; Vahrenhold, Jan. / Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies. In: Journal of Discrete Algorithms. 2010 ; Vol. 8, No. 3. pp. 259-272.

Bibtex

@article{0a739fca1aba4e79a40afd3f51f5e273,
title = "Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies",
abstract = "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.",
keywords = "Cache-oblivious algorithms, External-memory algorithms, Geometric graphs, Spanners, Well-separated pair decomposition",
author = "Fabian Gieseke and Joachim Gudmundsson and Jan Vahrenhold",
year = "2010",
doi = "10.1016/j.jda.2010.03.001",
language = "English",
volume = "8",
pages = "259--272",
journal = "Journal of Algorithms",
issn = "0196-6774",
publisher = "Academic Press",
number = "3",

}

RIS

TY - JOUR

T1 - Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

AU - Gieseke, Fabian

AU - Gudmundsson, Joachim

AU - Vahrenhold, Jan

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Cache-oblivious algorithms

KW - External-memory algorithms

KW - Geometric graphs

KW - Spanners

KW - Well-separated pair decomposition

UR - http://www.scopus.com/inward/record.url?scp=77955710007&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2010.03.001

DO - 10.1016/j.jda.2010.03.001

M3 - Journal article

AN - SCOPUS:77955710007

VL - 8

SP - 259

EP - 272

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 3

ER -

ID: 167918709