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.2016.22
URN: urn:nbn:de:0030-drops-67927
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6792/
Go to the corresponding LIPIcs Volume Portal

Chakraborty, Sankardeep ; Raman, Venkatesh ; Satti, Srinivasa Rao

Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits

pdf-format:
LIPIcs-ISAAC-2016-22.pdf (0.4 MB)

Abstract

Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014) reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of depth first search (DFS) of a graph on n vertices and m edges, taking O(m lg lg n) time using O(n) bits of space improving on the time bound of O(m lg n) due to Asano et al. Subsequently Banerjee et al. (COCOON 2016) gave an O(m + n) time implementation using O(m+n) bits, for DFS and its classical applications (including testing for biconnectivity, and finding cut vertices and cut edges). Recently, Kammer et al. (MFCS 2016) gave an algorithm for testing biconnectivity using O(n + min{m, n lg lg n}) bits in linear time.

In this paper, we consider O(n) bits implementations of the classical applications of DFS. These include the problem of finding cut vertices, and biconnected components, chain decomposition and st-numbering. Classical algorithms for them typically use DFS and some Omega(lg n) bits of information at each node. Our O(n)-bit implementations for these problems take O(m lg^c n lg lg n) time for some small constant c (c leq 3). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for space efficient graph algorithms.

BibTeX - Entry

@InProceedings{chakraborty_et_al:LIPIcs:2016:6792,
  author =	{Sankardeep Chakraborty and Venkatesh Raman and Srinivasa Rao Satti},
  title =	{{Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6792},
  URN =		{urn:nbn:de:0030-drops-67927},
  doi =		{10.4230/LIPIcs.ISAAC.2016.22},
  annote =	{Keywords: biconnectivity, st-number, chain decomposition, tree cover, space efficient algorithms, read-only memory}
}

Keywords: biconnectivity, st-number, chain decomposition, tree cover, space efficient algorithms, read-only memory
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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