En maximal oberoende uppsättning (MIS) kan upprätthållas i en föränderlig m-kant graf genom att helt enkelt omsätta den från grunden i O(m) tid efter varje uppdatering. Men kan det upprätthållas i tid sublinear i m i fullt dynamiska grafer? Vi besvarar denna grundläggande öppna fråga jakande. Vi presenterar en deterministisk algoritm med amortiserad uppdateringstid O(min~~~POS=TRUNC, m 3/4 }), där är en fast gräns på maximal grad i grafen och m är det (dynamiskt föränderliga) antalet kanter. Vi presenterar vidare en distribuerad implementation av vår algoritm med O(min ¡, m 3/4 }) amortized meddelande komplexitet, och O(1) amortized runda komplexitet och justering komplexitet (antalet hörn som ändrar sin utgång efter varje uppdatering). Detta stärker ett liknande resultat av Censor-Hillel, Haramaty och Karnin (PODC'16) som krävde ett antagande av en icke-adaptiv oöverträffad motståndare.
Till exempel, datastrukturen i REF upprätthåller den maximala oberoende uppsättningen av grafen deterministiskt i O(m 3/4 ) amorterad uppdateringstid (m är det dynamiska antalet kanter).
Fully dynamic maximal independent set with sublinear update time
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}