Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Dynamic spanning forest with worst-case update time: Adaptive, las vegas, and O(n1/2-∈) - Time
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2017 (English)In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2017, p. 1122-1129Conference paper, Published paper (Refereed)
Abstract [en]

We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee worst-case update time and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing O(√n) bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was O(√n(log log n)2/log n) [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an O(n04+o(1)) worst-case update time, where the o(1) term hides the O(√log log n/log n) factor. Our second algorithm is Las Vegas and guarantees an O(n0.49306) worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by Kapron et al. To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries. The key to our results is a decomposition of graphs into subgraphs that either have high expansion or sparse. This decomposition serves as an interface between recent developments on (static) flow computation and many old ideas in dynamic graph algorithms: On the one hand, we can combine previous dynamic graph techniques to get faster dynamic spanning forest algorithms if such decomposition is given. On the other hand, we can adapt fow-related techniques (e.g. those from [Khandekar, Rao and Vazirani STOC'06], [Peng SODA'16], and [Orecchia and Zhu SODA'14]) to maintain such decomposition. To the best of our knowledge, this is the first time these flow techniques are used in fully dynamic graph algorithms.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2017. p. 1122-1129
Series
Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0737-8017
Keywords [en]
Dynamic spanning forest, Graph decomposition, Local graph partitioning, Sparse recovery
National Category
Other Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-212107DOI: 10.1145/3055399.3055447ISI: 000440317600098Scopus ID: 2-s2.0-85024375894ISBN: 9781450345286 (print)OAI: oai:DiVA.org:kth-212107DiVA, id: diva2:1133723
Conference
49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, 19 June 2017 through 23 June 2017
Funder
EU, European Research Council, 715672Swedish Research Council, 2015-04659
Note

QC 20170816

Available from: 2017-08-16 Created: 2017-08-16 Last updated: 2018-08-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nanongkai, DanuponSaranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 11 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf