Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time

Publikation: Working paperForskning

Dokumenter

  • 08-11

    Forlagets udgivne version, 181 KB, PDF-dokument

Vi betragter problemet med at finde Wiener-indekset af en graf, defineret som summen af afstande mellem alle grafens knudepar. Det er et åbent problem, om Wiener-indekset af en planar graf kan findes i subkvadratisk tid. Vi løser dette problem ved at præsentere en algoritme med O(n^2*log log n/log n) køretid og O(n) pladsforbrug, hvor n er antal knuder i grafen.
OriginalsprogEngelsk
Udgivelses stedDIKU
Sider1-10
Antal sider10
StatusUdgivet - 2008

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


Ingen data tilgængelig

ID: 9617991