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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يوليو 2018
منشور خارجيًانعم
الحدث45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, التشيك
المدة: ٩ يوليو ٢٠١٨١٣ يوليو ٢٠١٨

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت107

!!Conference

!!Conference45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
الدولة/الإقليمالتشيك
المدينةPrague
المدة٩/٠٧/١٨١٣/٠٧/١٨

All Science Journal Classification (ASJC) codes

  • !!Software

قم بذكر هذا