Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces

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 languageEnglish
Title of host publicationCollection of Abstracts of the 24th European Workshop on Computational Geometry : EuroCG, LORIA, Nancy, France, March 18-20, 2008
EditorsSylvain Petitjean
Number of pages4
PublisherLORIA, Nancy, France
Publication date2008
Pages123-126
Publication statusPublished - 2008
EventEuropean Workshop on Computational Geometry (EuroCG) - Nancy, France
Duration: 18 Mar 200820 Mar 2008
Conference number: 24

Conference

ConferenceEuropean Workshop on Computational Geometry (EuroCG)
Number24
Country/TerritoryFrance
CityNancy
Period18/03/200820/03/2008

Fingerprint

Dive into the research topics of 'Computing the Dilation of Edge-Augmented Graphs Embedded in Metric Spaces'. Together they form a unique fingerprint.

Cite this