文章基本信息
- 标题：Constant-Time Dynamic (Î"+1)-Coloring
- 本地全文：下载
- 作者：Monika Henzinger ; Pan Peng
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：154
- 页码：53:1-53:18
- DOI：10.4230/LIPIcs.STACS.2020.53
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Î"+1)-vertex coloring of a graph with maximum degree at most Î". This improves upon the previous O(log Î")-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Î"-coloring exists in a dynamically changing graph with maximum degree at most Î" takes Ω(log n) time per operation.
- 关键词：Dynamic graph algorithms; Graph coloring; Random sampling
