License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.59
URN: urn:nbn:de:0030-drops-82607
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8260/
Go to the corresponding LIPIcs Volume Portal

Nakamura, Kengo

Fully Dynamic Connectivity Oracles under General Vertex Updates

pdf-format:
LIPIcs-ISAAC-2017-59.pdf (0.5 MB)

Abstract

We study the following dynamic graph problem: given an undirected graph G, we maintain a connectivity oracle between any two vertices in G under any on-line sequence of vertex deletions and insertions with incident edges. We propose two algorithms for this problem: an amortized update time deterministic one and a worst case update time Monte Carlo one.
Both of them allow an arbitrary number of new vertices to insert.
The update time complexity of the former algorithm is no worse than the existing algorithms, which allow only limited number of vertices to insert.
Moreover, for relatively dense graphs, we can expect that the update time bound of the former algorithm meets a lower bound,
and that of the latter algorithm can be seen as a substantial improvement of the existing result by introducing randomization.

BibTeX - Entry

@InProceedings{nakamura:LIPIcs:2017:8260,
  author =	{Kengo Nakamura},
  title =	{{Fully Dynamic Connectivity Oracles under General Vertex Updates}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8260},
  URN =		{urn:nbn:de:0030-drops-82607},
  doi =		{10.4230/LIPIcs.ISAAC.2017.59},
  annote =	{Keywords: Dynamic Graph, Connectivity, Depth-First Search}
}

Keywords: Dynamic Graph, Connectivity, Depth-First Search
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

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