Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-63953

; ; ;

Faster Worst Case Deterministic Dynamic Connectivity



We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(sqrt{(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(sqrt{n}). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

BibTeX - Entry

  author =	{Casper Kejlberg-Rasmussen and Tsvi Kopelowitz and Seth Pettie and Mikkel Thorup},
  title =	{{Faster Worst Case Deterministic Dynamic Connectivity}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-63953},
  doi =		{10.4230/LIPIcs.ESA.2016.53},
  annote =	{Keywords: dynamic graph, spanning tree}

Keywords: dynamic graph, spanning tree
Seminar: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI