Sammanfattning För en oviktad oriktad graf G = (V, E), och ett par positiva heltal α ≥ 1, β ≥ 0, en subgraf G = (V, H ), H  på E, kallas en (α, β)-panner av G om för varje par av hörn u, v V, dist G (u, v) Det visades i [21] att för alla > 0, δ = 1, 2,............................................................................. ., Det finns ett heltal β = β(, δ) sådan att för varje nvertex graf G finns det en (1 +, β)-spanner G med O(n 1+1/σ ) kanter. Ett effektivt distribuerat protokoll för konstruktion (1 +, β)-spanners utformades i [19]. Löptiden och kommunikations komplexiteten i det protokollet är O(n 1 + ρ ) respektive O( skan ρ ), där ρ är en ytterligare kontrollparameter i protokollet som endast påverkar additiva termen β. I detta dokument utformar vi ett protokoll med en drastiskt förbättrad körtid (O(n ρ ) i motsats till O(n 1+ρ )) för konstruktion (1 +, β)-spanners. Vårt protokoll har samma kommunikations komplexitet som protokollet av [19], och det konstruerar skiftnycklar med i huvudsak samma egenskaper som de skiftnycklar som konstrueras av protokollet av [19]. Protokollet kan enkelt utvidgas till ett parallellt genomförande som körs i O(log n + ( på engelska) · n ρ log n) / p) tid med hjälp av p-processorer i EREW PRAM-modellen. I synnerhet, när antalet processorer, p, är minst A · n ρ, körtiden för algoritmen är O(log n). Vi visar också att vårt protokoll för att bygga (1 +, β)-spanners kan anpassas till den strömmande modellen, och utforma en strömmande algoritm som använder ett konstant antal passer och O(n 1+1/σ · log n) bitar av utrymme för att beräkna alla-par-nästan kortaste-vägar av längd som mest genom en multiplikativ faktor (1 + ) och en additiv term av β större än de kortaste vägar. Vår algoritm bearbetar varje kant i tiden O(n ρ ), för en godtyckligt liten ρ > 0. Den enda tidigare kända algoritmen för problemet [23] konstruerar banor av längd δ gånger större än de kortaste banorna, har samma utrymmeskrav som vår algoritm, men kräver O(n 1+1/σ ) tid för bearbetning av varje kant av inmatningskurvan. Men algoritmen [23] använder bara ett pass över inmatningen, i motsats till det konstanta antalet pass i vår algoritm. 1 Vi visar också att all streaming algoritm för o(n)-ungefärlig distans beräkning kräver (n) bitar av utrymme.
I oviktade oriktade grafer kan pannkonstruktionen av REF användas för att beräkna (1 + o(1))-ungefärlig SSSP med hjälp av O(1)-pass och O(n 1+o(1) ) utrymme.
Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}