Abstract
Let G = (V,E) be an undirected graph with n vertices embedded in a metric space. We consider the problem of adding a shortcut edge in G that minimizes the dilation of the resulting graph. The fastest algorithm to date for this problem has O(n^4) running time and uses O(n^2) space. We show how to improve running time to O(n^3*log n) while maintaining quadratic space requirement. In fact, our algorithm not only determines the best shortcut but computes the dilation of G U {(u,v)} for every pair of distinct vertices u and v.
Original language | English |
---|---|
Title of host publication | Collection of Abstracts of the 24th European Workshop on Computational Geometry : EuroCG, LORIA, Nancy, France, March 18-20, 2008 |
Editors | Sylvain Petitjean |
Number of pages | 4 |
Publisher | LORIA, Nancy, France |
Publication date | 2008 |
Pages | 123-126 |
Publication status | Published - 2008 |
Event | European Workshop on Computational Geometry (EuroCG) - Nancy, France Duration: 18 Mar 2008 → 20 Mar 2008 Conference number: 24 |
Conference
Conference | European Workshop on Computational Geometry (EuroCG) |
---|---|
Number | 24 |
Country/Territory | France |
City | Nancy |
Period | 18/03/2008 → 20/03/2008 |