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

Datalogisk Institut

9 Citationer (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.

Originalsprog	Engelsk
Titel	24th Annual European Symposium on Algorithms (ESA 2016)
Redaktører	Piotr Sankowski, Christos Zaroliagis
Antal sider	15
Forlag	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato	1 aug. 2016
Sider	53:1-53:15
Artikelnummer	53
ISBN (Trykt)	978-3-95977-015-6
DOI	https://doi.org/10.4230/LIPIcs.ESA.2016.53
Status	Udgivet - 1 aug. 2016
Begivenhed	European symposium on algorithms - , Danmark Varighed: 22 aug. 2016 → 26 aug. 2016 Konferencens nummer: 24 http://conferences.au.dk/algo16/esa/

Konference

Konference	European symposium on algorithms
Nummer	24
Land/Område	Danmark
Periode	22/08/2016 → 26/08/2016
Internetadresse	http://conferences.au.dk/algo16/esa/

Navn	Leibniz International Proceedings in Informatics
Vol/bind	57
ISSN	1868-8969

Adgang til dokumentet

10.4230/LIPIcs.ESA.2016.53Licens: CC BY

Faster Worst Case Deterministic Dynamic Connectivity*Forlagets udgivne version, 600 KBLicens: CC BY

Citationsformater

Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S., & Thorup, M. (2016). Faster worst case deterministic dynamic connectivity. I P. Sankowski, & C. Zaroliagis (red.), 24th Annual European Symposium on Algorithms (ESA 2016) (s. 53:1-53:15). [53] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Bind 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). red. / Piotr Sankowski; Christos Zaroliagis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. s. 53:1-53:15 53 (Leibniz International Proceedings in Informatics, Bind 57).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Kejlberg-Rasmussen, C, Kopelowitz, T, Pettie, S & Thorup, M 2016, Faster worst case deterministic dynamic connectivity. i P Sankowski & C Zaroliagis (red), 24th Annual European Symposium on Algorithms (ESA 2016)., 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, bind 57, s. 53:1-53:15, European symposium on algorithms, Danmark, 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. I Sankowski P, Zaroliagis C, red., 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. s. 53:1-53:15. 53. (Leibniz International Proceedings in Informatics, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater