Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

Publikation: Working paperForskning

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

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


Ingen data tilgængelig

ID: 9618617