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

DOI10.1016/j.jda.2010.03.001zbMath1227.05235OpenAlexW2054204720MaRDI QIDQ988687

Jan Vahrenhold, Joachim Gudmundsson, Fabian Gieseke

Publication date: 18 August 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.03.001

zbMATH Keywords

geometric graphsspannerscache-oblivious algorithmswell-separated pair decompositionexternal-memory algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sparse spanners of weighted graphs
• The buffer tree: A technique for designing batched external data structures
• I/O-efficient well-separated pair decomposition and applications
• Algorithms and Data Structures for External Memory
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• A Data Structure for Dynamically Maintaining Rooted Trees
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
• I/O-Efficiently Pruning Dense Spanners
• STACS 2005
• Lower bounds for computing geometric spanners and approximate shortest paths
• Improved algorithms for constructing fault-tolerant spanners

This page was built for publication: Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies