En α-spanner i en graf G är en undergraf H så att H bevarar alla avstånd av G inom en faktor av α. I detta dokument ger vi helt dynamiska algoritmer för att upprätthålla en skiftnyckel H i en graf G som genomgår kantinsättningar och raderingar med värsta tänkbara garantier om körtiden efter varje uppdatering. I synnerhet, våra algoritmer upprätthålla: • en 3-spanner med Õ(n 1+1/2 ) kanter med värsta-fall uppdateringstid Õ(n 3/4 ), eller • en 5-spanner med Õ(n 1+1/3 ) kanter med värsta-fall uppdateringstid Õ(n 5/9 ). Dessa storlek / stretch kompromisser är bästa möjliga (upp till logaritmiska faktorer). De kan utvidgas till den viktade inställningen till en mycket liten kostnad. Våra algoritmer är randomiserade och korrekta med stor sannolikhet mot en omedveten motståndare. Vi utökar också våra tekniker ytterligare för att bygga en 5-spanner med suboptimal storlek / stretch kompromiss, men förbättrade värsta fall uppdateringstid. Såvitt vi vet är detta de första dynamiska skiftnyckelalgoritmerna med sublinjära sämsta-fall-uppdateringstidsgarantier. Eftersom det är känt hur man underhåller en skiftnyckel med hjälp av små amorterade men stora värsta fall uppdateringstid [Baswana et al. SODA'08], att få algoritmer med starka värsta fall gränser, som presenteras i detta dokument, verkar vara nästa naturliga steg för detta problem.
REF gav de första dynamiska algoritmerna med sublinjär uppdateringstid i värsta fall för 3-spanner och 5-spanner.
Fully Dynamic Spanners with Worst-Case Update Time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}