The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition
From MaRDI portal
Publication:3569878
DOI10.1007/978-3-642-13731-0_6zbMATH Open1285.68122arXiv0905.2605OpenAlexW3121875547MaRDI QIDQ3569878
Author name not available (Why is that?)
Publication date: 22 June 2010
Published in: (Search for Journal in Brave)
Abstract: A spanner graph on a set of points in 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 -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
No records found.
No records found.
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)
