1 Search Results for "K. Mehta, Shashank"

Document

DOI: 10.4230/LIPIcs.STACS.2019.42

Depth First Search in the Semi-streaming Model

Authors: Shahbaz Khan and Shashank K. Mehta

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract

Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical algorithm for building a DFS tree requires O(m+n) time for a given undirected graph G having n vertices and m edges. In the streaming model, an algorithm is allowed several passes (preferably single) over the input graph having a restriction on the size of local space used. Now, a DFS tree of a graph can be trivially computed using a single pass if O(m) space is allowed. In the semi-streaming model allowing O(n) space, it can be computed in O(n) passes over the input stream, where each pass adds one vertex to the DFS tree. However, it remains an open problem to compute a DFS tree using o(n) passes using o(m) space even in any relaxed streaming environment. We present the first semi-streaming algorithms that compute a DFS tree of an undirected graph in o(n) passes using o(m) space. We first describe an extremely simple algorithm that requires at most ceil[n/k] passes to compute a DFS tree using O(nk) space, where k is any positive integer. For example using k=sqrt{n}, we can compute a DFS tree in sqrt{n} passes using O(n sqrt{n}) space. We then improve this algorithm by using more involved techniques to reduce the number of passes to ceil[h/k] under similar space constraints, where h is the height of the computed DFS tree. In particular, this algorithm improves the bounds for the case where the computed DFS tree is shallow (having o(n) height). Moreover, this algorithm is presented in form of a framework that allows the flexibility of using any algorithm to maintain a DFS tree of a stored sparser subgraph as a black box, which may be of an independent interest. Both these algorithms essentially demonstrate the existence of a trade-off between the space and number of passes required for computing a DFS tree. Furthermore, we evaluate these algorithms experimentally which reveals their exceptional performance in practice. For both random and real graphs, they require merely a few passes even when allowed just O(n) space.

Cite as

Shahbaz Khan and Shashank K. Mehta. Depth First Search in the Semi-streaming Model. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.STACS.2019.42,
  author =	{Khan, Shahbaz and K. Mehta, Shashank},
  title =	{{Depth First Search in the Semi-streaming Model}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.42},
  URN =		{urn:nbn:de:0030-drops-102818},
  doi =		{10.4230/LIPIcs.STACS.2019.42},
  annote =	{Keywords: Depth First Search, DFS, Semi-Streaming, Streaming, Algorithm}
}

Refine by Author
1 K. Mehta, Shashank
1 Khan, Shahbaz

Refine by Classification
1 Theory of computation → Data structures design and analysis
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Streaming, sublinear and near linear time algorithms

Refine by Keyword
1 Algorithm
1 DFS
1 Depth First Search
1 Semi-Streaming
1 Streaming

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "K. Mehta, Shashank"

Depth First Search in the Semi-streaming Model

Abstract

Cite as

Thanks for your feedback!

Could not send message