Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Publikation: Working paperForskning

Dokumenter

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.
OriginalsprogEngelsk
Udgivelses stedKøbenhavn
UdgiverDepartment of Computer Science, University of Copenhagen
Antal sider25
StatusUdgivet - 2008

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 9618113