Fully dynamic MIS in uniformly sparse graphs

Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity α, the amortized update time of our algorithm is O(α2 · log2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of “real world” graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m3/8−, for any constant > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m1/2.

שפה מקוריתאנגלית
כותר פרסום המארח45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
עורכיםChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
מסת"ב (אלקטרוני)9783959770767
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יולי 2018
פורסם באופן חיצוניכן
אירוע45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, צ'כיה
משך הזמן: 9 יולי 201813 יולי 2018

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך107

כנס

כנס45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
מדינה/אזורצ'כיה
עירPrague
תקופה9/07/1813/07/18

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

פורמט ציטוט ביבליוגרפי