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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Lad G = (V,E) være en ikke-orienteret graf med n knuder indlejret i et metrisk rum. Vi betragter problemet med at finde en shortcut-kant i G, der minimerer omvejen (dilation) af den resulterende graf. Den hurtigste algoritme for dette problem har O(n^4) køretid og bruger O(n^2) plads. Vi viser, hvordan køretiden kan forbedres til O(n^3*log n) med samme pladsforbrug. Vores algoritme finder ikke kun det bedste shortcut, men bestemmer omvejen af G U {(u,v)} for alle par af forskellige knuder u og v.
OriginalsprogEngelsk
TitelCollection of Abstracts of the 24th European Workshop on Computational Geometry : EuroCG, LORIA, Nancy, France, March 18-20, 2008
RedaktørerSylvain Petitjean
Antal sider4
ForlagLORIA, Nancy, France
Publikationsdato2008
Sider123-126
StatusUdgivet - 2008
BegivenhedEuropean Workshop on Computational Geometry (EuroCG) - Nancy, Frankrig
Varighed: 18 mar. 200820 mar. 2008
Konferencens nummer: 24

Konference

KonferenceEuropean Workshop on Computational Geometry (EuroCG)
Nummer24
LandFrankrig
ByNancy
Periode18/03/200820/03/2008

ID: 9617833