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

Chakraborty, Sankardeep ; Sadakane, Kunihiko

Indexing Graph Search Trees and Applications

pdf-format:
LIPIcs-MFCS-2019-67.pdf (0.4 MB)

Abstract

We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having n vertices and m edges while supporting various DFS related queries efficiently in the RAM with logarithmic word size. We study this problem in two well-known models: indexing and encoding models. While most of these queries can be supported easily in constant time using O(n lg n) bits of extra space, our goal here is, more specifically, to beat this trivial O(n lg n) bit space bound, yet not compromise too much on the running time of these queries. In the indexing model, the space bound of our solution involves the quantity m, hence, we obtain different bounds for sparse and dense graphs respectively. In the encoding model, we first give a space lower bound, followed by an almost optimal data structure with extremely fast query time. Central to our algorithm is a partitioning of the DFS tree into connected subtrees, and a compact way to store these connections. Finally, we also apply these techniques to compactly index the shortest path structure, biconnectivity structures among others.

BibTeX - Entry

@InProceedings{chakraborty_et_al:LIPIcs:2019:11011,
  author =	{Sankardeep Chakraborty and Kunihiko Sadakane},
  title =	{{Indexing Graph Search Trees and Applications}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{67:1--67:14},
  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/11011},
  URN =		{urn:nbn:de:0030-drops-110112},
  doi =		{10.4230/LIPIcs.MFCS.2019.67},
  annote =	{Keywords: Depth First Search Tree, Compact Data Structures, Encoding Schemes}
}

Keywords: Depth First Search Tree, Compact Data Structures, Encoding Schemes
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