Faster worst case deterministic dynamic connectivity

Casper Kejlberg-Rasmussen; Tsvi Kopelowitz; Seth Pettie; Mikkel Thorup

doi:10.4230/LIPIcs.ESA.2016.53

Faster worst case deterministic dynamic connectivity

Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup

Department of Computer Science

9 Citations (Scopus)

44 Downloads (Pure)

Abstract

We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(√n(log log n)²/log n) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(√n). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

Original language	English
Title of host publication	24th Annual European Symposium on Algorithms (ESA 2016)
Editors	Piotr Sankowski, Christos Zaroliagis
Number of pages	15
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	1 Aug 2016
Pages	53:1-53:15
Article number	53
ISBN (Print)	978-3-95977-015-6
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2016.53
Publication status	Published - 1 Aug 2016
Event	European symposium on algorithms - , Denmark Duration: 22 Aug 2016 → 26 Aug 2016 Conference number: 24 http://conferences.au.dk/algo16/esa/

Conference

Conference	European symposium on algorithms
Number	24
Country/Territory	Denmark
Period	22/08/2016 → 26/08/2016
Internet address	http://conferences.au.dk/algo16/esa/

Series	Leibniz International Proceedings in Informatics
Volume	57
ISSN	1868-8969

Access to Document

10.4230/LIPIcs.ESA.2016.53Licence: CC BY

Faster Worst Case Deterministic Dynamic Connectivity*Final published version, 600 KBLicence: CC BY

Cite this

Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S., & Thorup, M. (2016). Faster worst case deterministic dynamic connectivity. In P. Sankowski, & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016) (pp. 53:1-53:15). [53] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Vol. 57 https://doi.org/10.4230/LIPIcs.ESA.2016.53

Faster worst case deterministic dynamic connectivity. / Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth et al.

24th Annual European Symposium on Algorithms (ESA 2016). ed. / Piotr Sankowski; Christos Zaroliagis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. p. 53:1-53:15 53 (Leibniz International Proceedings in Informatics, Vol. 57).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Kejlberg-Rasmussen, C, Kopelowitz, T, Pettie, S & Thorup, M 2016, Faster worst case deterministic dynamic connectivity. in P Sankowski & C Zaroliagis (eds), 24th Annual European Symposium on Algorithms (ESA 2016)., 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, vol. 57, pp. 53:1-53:15, European symposium on algorithms, Denmark, 22/08/2016. https://doi.org/10.4230/LIPIcs.ESA.2016.53

Kejlberg-Rasmussen C, Kopelowitz T, Pettie S, Thorup M. Faster worst case deterministic dynamic connectivity. In Sankowski P, Zaroliagis C, editors, 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. p. 53:1-53:15. 53. (Leibniz International Proceedings in Informatics, Vol. 57). doi: 10.4230/LIPIcs.ESA.2016.53

@inproceedings{15482fca85b5452ab445186af747081c,

title = "Faster worst case deterministic dynamic connectivity",

abstract = "We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(√n(log log n)2/log n) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(√n). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.",

author = "Casper Kejlberg-Rasmussen and Tsvi Kopelowitz and Seth Pettie and Mikkel Thorup",

year = "2016",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.ESA.2016.53",

language = "English",

isbn = "978-3-95977-015-6",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "53:1--53:15",

editor = "Piotr Sankowski and Christos Zaroliagis",

booktitle = "24th Annual European Symposium on Algorithms (ESA 2016)",

note = "European symposium on algorithms ; Conference date: 22-08-2016 Through 26-08-2016",

url = "http://conferences.au.dk/algo16/esa/",

}

TY - GEN

T1 - Faster worst case deterministic dynamic connectivity

AU - Kejlberg-Rasmussen, Casper

AU - Kopelowitz, Tsvi

AU - Pettie, Seth

AU - Thorup, Mikkel

N1 - Conference code: 24

PY - 2016/8/1

Y1 - 2016/8/1

N2 - We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(√n(log log n)2/log n) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(√n). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

AB - We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(√n(log log n)2/log n) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(√n). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

U2 - 10.4230/LIPIcs.ESA.2016.53

DO - 10.4230/LIPIcs.ESA.2016.53

M3 - Article in proceedings

SN - 978-3-95977-015-6

T3 - Leibniz International Proceedings in Informatics

SP - 53:1-53:15

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - European symposium on algorithms

Y2 - 22 August 2016 through 26 August 2016

ER -

Faster worst case deterministic dynamic connectivity

Abstract

Conference

Access to Document

Fingerprint

Cite this