The emergence of sparse spanners and greedy well-separated pair decomposition

DOI10.1007/978-3-642-13731-0_6zbMATH Open1285.68122arXiv0905.2605OpenAlexW3121875547MaRDI QIDQ3569878FDOQ3569878

Authors:

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A spanner graph on a set of points in $R^d$ contains a shortest path between any pair of points with length at most a constant factor of their Euclidean distance. In this paper we investigate new models and aim to interpret why good spanners 'emerge' in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. Our main result is to show that if edges are built in an arbitrary order but an edge is built if and only if its endpoints are not 'close' to the endpoints of an existing edge, the graph is a $(1+eps)$-spanner with a linear number of edges, constant average degree, and the total edge length as a small logarithmic factor of the cost of the minimum spanning tree. As a side product, we show a simple greedy algorithm for constructing optimal size well-separated pair decompositions that may be of interest on its own.

Full work available at URL: https://arxiv.org/abs/0905.2605

Recommendations

• The emergence of sparse spanners and well-separated pair decomposition under anarchy
• Distribution-sensitive construction of the greedy spanner
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Distribution-sensitive construction of the greedy spanner
• scientific article; zbMATH DE number 1617269

zbMATH Keywords

greedy algorithmspannerwell-separated pair decomposition

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10)

Cited In (7)

• The emergence of sparse spanners and well-separated pair decomposition under anarchy
• Separator-Based Sparsification II: Edge and Vertex Connectivity
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
• Local routing in spanners based on WSPDs
• On Pairwise Spanners
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Local routing in WSPD-based spanners

This page was built for publication: The emergence of sparse spanners and greedy well-separated pair decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569878)