Låt G vara en oviktad, oriktad graf. En additiv k-spanner av G är en subgraf H som approximerar alla avstånd mellan par av noder upp till ett additivt fel av `k, det vill säga, det uppfyller d H pu, vq  på G pu, vq`k för alla noder u, v, där d är den kortaste vägen avståndet. Vi ger en deterministisk algoritm som konstruerar en additiv Op1q-spanner med O'n 4{3  och e dges i O'n 2  på ime. Detta bör jämföras med den randomiserade Monte Carlo-algoritmen av Woodruff [ICAP 2010] som ger en additiv 6-spanner med O'n 4{3 log 3 n  på förväntad tid O`n 2 log 2 n  på. En pα, βq-ungefärlig avstånd oracle för G är en datastruktur som stöder följande avstånd frågor mellan par av noder i G. Med tanke på två noder u, v det kan i konstant tid beräkna ett avstånd uppskattas som uppfyller d  skad  och αd`β där d är avståndet mellan u och v i G. Sommer [ICAP 2016] gav en randomiserad Monte Carlo p2, 1q-distans oracle av storlek O`n 5{3 poly log n. n förväntad tid O`n 2 poly log n. Som en tillämpning av tillsatsen Op1q-spanner vi förbättra konstruktionen av Sommer [ICAP 2016] och ge en Las Vegas p2, 1q-distans oracle av storlek O`n 5{3  på tiden O`n 2. Detta innebär också en algoritm som i O'n 2  tillg ives ungefärligt avstånd för alla par av noder i G förbättra på O`n 2 log n  på Algorithm av Baswana och Kavitha [SICOMP 2010].
Byggtiden förbättrades nyligen till O(n 2 ) av Knudsen REF.
Additive Spanners and Distance Oracles in Quadratic Time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}