Abstract
Lad G være en plan graf, hvor hver kant er et linjestykke. Vi betragter problemet med at finde den maksimale omvej (detour) i G, defineret som maksimum over alle par af forskellige punkter p og q i G (knuder såvel som indre punkter i kanter) af forholdet mellem afstanden mellem p og q i G og afstanden |pq|. Den hurtigste algoritme for dette problem har O(n^2) køretid, hvor n er antallet af knuder i G. Vi viser, hvordan man kan opnå O(n^{3/2}*(log n)^3) forventet køretid. Vi viser også, at hvis G har begrænset treewidth, så kan dens maksimale omvej bestemmes i O(n(log n)^3) forventet tid.
| Originalsprog | Engelsk |
|---|---|
| Udgivelsessted | København |
| Udgiver | Department of Computer Science, University of Copenhagen |
| Antal sider | 25 |
| Status | Udgivet - 2008 |