Abstrakt. En (α, β)-spanner av en oviktad graf G är en subgraf H som förvränger avstånden i G upp till en multiplikativ faktor av α och en additiv term β. Det är välkänt att varje graf innehåller en (multiplikativ) (2k − 1, 0)-spanner i storlek O(n 1+1/k ) och en (additiv) (1, 2)-spanner i storlek O(n 3/2 ). Det finns dock inga andra additiva skiftnycklar. I denna artikel utvecklar vi ett par nya tekniker för att konstruera (α, β)-spanners. Vårt första resultat är en tillsats (1, 6)-spanner i storlek O(n 4/3 ). Konstruktionsalgoritmen kan förstås som en ekonomisk agent som tilldelar kostnader och värden till vägar i grafen, köper prisvärda vägar och ignorerar dyra sådana, som intuitivt väl approximeras av vägar som redan köpts. Vi visar att denna väg köpa algoritm kan parameteriseras på olika sätt för att ge andra sparseness-snedvridning kompromisser. Vårt andra resultat tar upp problemet med vilka (α, β)-spanners kan beräknas effektivt, helst i linjär tid. Vi visar att för alla k, a (k, k − 1)-spanner med storlek O (kn 1+1/k ) kan hittas i linjär tid, och, vidare, att i ett distribuerat nätverk algoritmen slutar i ett konstant antal rundor. Tidigare skiftnyckelkonstruktioner med liknande prestanda hade ungefär dubbelt så stor multiplikativ förvrängning.
Den glesaste additiv spannare känd är en 6-additiv spannare i storlek O(n 4/3 ) som gavs av Baswana, Kavitha, Mehlhorn, och Pettie REF.
Additive spanners and (α, β)-spanners
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}