2020/07/24 by Gudmundsson, Joachim, Wong, Sampson · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.12350
Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of k edges, which k edges do we add to produce a minimum-dilation graph? The special case where k=1 has been studied in the past, but no major breakthroughs have been made for k > 1. We provide the first positive result, an O(k)-approximation algorithm that runs in O(n3 log n) time.