Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces

Givet en graf indlejret i et metrisk rum, dens omvej (dilation) er maksimum over alle forskellige knudepar af forholdet mellem afstanden mellem dem i grafen og metrik-afstanden mellem dem. Givet en sådan graf G med n knuder og m kanter og bestående af højst to sammenhængende komponenter, betragter vi problemet med at udvide G med en kant således, at den resulterende graf har minimal omvej. Vi viser, at man kan finde en sådan kant i O((n^4*log n)/m^{0.5}) tid og lineær plads, hvilket løser et åbent problem om, hvorvidt en lineær plads-algoritme med o(n^4) køretid eksisterer. Vi viser, at O(n^2*log n) køretid kan opnås, hvis G er en simpel vej eller foreningen af to knude-disjunkte simple veje. Endelig viser vi, hvordan man kan finde en kant, der maksimerer omvejen i den resulterende graf i O(n^3) tid og O(n^2) plads og i O(n^3*log n) tid med lineær plads.