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.MFCS.2019.65
URN: urn:nbn:de:0030-drops-110096
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11009/
Go to the corresponding LIPIcs Volume Portal

Baswana, Surender ; Gupta, Shiv ; Tulsyan, Ayush

Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

pdf-format:
LIPIcs-MFCS-2019-65.pdf (0.5 MB)

Abstract

We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

BibTeX - Entry

@InProceedings{baswana_et_al:LIPIcs:2019:11009,
  author =	{Surender Baswana and Shiv Gupta and Ayush Tulsyan},
  title =	{{Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11009},
  URN =		{urn:nbn:de:0030-drops-110096},
  doi =		{10.4230/LIPIcs.MFCS.2019.65},
  annote =	{Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant}
}

Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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