Vi presenterar två algoritmer för dynamisk underhåll av en spännande skog av en graf som genomgår kantinsättningar och raderingar. Våra algoritmer garanterar i värsta fall uppdateringstid och arbetar mot en adaptiv motståndare, vilket innebär att en edge update kan bero på tidigare utgångar av algoritmerna. Vi ger den första polynom förbättring över den långvariga O ( ε n) bundet av [Frederickson STOC'83, Eppstein, Galil, Italiano och Nissenzweig FOCS'92] för sådan typ av algoritmer. Den tidigare bästa förbättringen var O( n(log log n) 2 /log n) [Kejlberg-Rasmussen, Kopelowitz, Pettie och Thorup ESA'16]. Vi noterar dock att dessa gränser erhölls genom deterministiska algoritmer medan våra algoritmer randomiserades. Vår första algoritm är Monte Carlo och garanterar en O(n 0.4+o(1) ) värsta fall uppdateringstid, där o(1) termen döljer O( log n/log n) faktor. Vår andra algoritm är Las Vegas och * Den fullständiga versionen av detta dokument finns på https://arxiv.org/abs/1611.03745
Nyligen presenterade Nanongkai och Saranurak REF en randomiserad Las-Vegas algoritm för dynamisk MSF med en förväntad värsta-fall uppdateringstid på O(n 1 2 −ε ) för vissa konstant ε > 0.
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}