Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time
Publikation: Working paper › Forskning
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.
Originalsprog | Engelsk |
---|---|
Udgivelsessted | DIKU |
Sider | 1-10 |
Antal sider | 10 |
Status | Udgivet - 2008 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 9617991