Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time
Publikation: Working paper › Forskning
Dokumenter
- 08-16
Forlagets udgivne version, 368 KB, PDF-dokument
Vi løser tre åbne problemer ved at bevise eksistensen af algoritmer med subkvadratisk køretid til at bestemme Wiener-indekset (summen af APSP-afstande) og diameteren (maksimal afstand mellem knudepar) af en planar graf med ikke-negative kantvægte samt stretch-faktoren af en plan geometrisk graf (maksimum over alle par af forskellige knuder af forholdet mellem graf-afstanden og den Euklidiske afstand mellem de to knuder). Mere præcist viser vi, at Wiener-indekset og diameteren kan bestemmes i O(n^2*(log log n)^4/log n) worst-case-tid, og at stretch-faktoren kan bestemmes i O(n^2*(log log n)^4/log n) forventet tid, hvor n er antallet af knuder. Vi viser også, hvordan man kan bestemme Wiener-indekset og diameteren af en ikke-vægtet delgraf-afsluttet n^{0.5}-separabel graf i O(n^2*log log n/log n) worst-case-tid og O(n) plads.
Originalsprog | Engelsk |
---|---|
Udgivelsessted | København |
Udgiver | Department of Computer Science, University of Copenhagen |
Antal sider | 30 |
Status | Udgivet - 2008 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 9618617