Improved space efficient algorithms for BFS, DFS and applications

DOI10.1007/978-3-319-42634-1_10MaRDI QIDQ2817855zbMATH OpenOpenAlexFDO

Authors Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04718

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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. We continue this line of work focusing on space. Our first result is a simple data structure that can maintain any subset $S$ of a universe of $n$ elements using $n+o(n)$ bits and support in constant time, apart from the standard insert, delete and membership queries, the operation {it findany} that finds and returns any element of the set (or outputs that the set is empty). Using this we give a BFS implementation that takes $O(m+n)$ time using at most $2n+o(n)$ bits. Later, we further improve the space requirement of BFS to at most $1.585n+o(n)$ bits. We demonstrate the use of our data structure by developing another data structure using it that can represent a sequence of $n$ non-negative integers $x_1,x_2,ldots{x}_n$ using at most $su{m}_{i=1}^n{x}_i+2n+o(su{m}_{i=1}^n{x}_i+n)$ bits and, in constant time, determine whether the $i$-th element is $0$ or decrement it otherwise. We also discuss an algorithm for finding a minimum weight spanning tree of a weighted undirected graph using at most $n+o(n)$ bits. We also provide an implementation for DFS that takes $O(m+n)$ time and $O(nlg(m/n))$ bits. Using this DFS algorithm and other careful implementations, we can test biconnectivity, 2-edge connectivity, and determine cut vertices, bridges etc among others, essentially within the same time and space bounds required for DFS. These improve the space required for earlier implementations from $Omega(nlgn)$ bits.

Recommendations

• Space efficient linear time algorithms for BFS, DFS and applications
• Biconnectivity, chain decomposition and st-numbering using O(n) bits
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Depth-First Search Using O(n) Bits
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits

Cites work

• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• A Framework for Dynamizing Succinct Data Structures
• A simple test on 2-vertex- and 2-edge-connectivity
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Computational Complexity
• Constant-work-space algorithms for geometric problems
• Depth-First Search Using O(n) Bits
• scientific article; zbMATH DE number 2185599 (Why is no real title available?)
• Introduction to algorithms.
• Listing all maximal cliques in large sparse real-world graphs
• New time-space upperbounds for directed reachability in high-genus and H-minor-free graphs
• Optimal time-space tradeoff for the 2D convex-hull problem
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Space-efficient basic graph algorithms
• Space-time trade-offs for stack-based algorithms
• Succinct data structures for searchable partial sums with optimal worst-case performance
• Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs
• Undirected connectivity in log-space
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(20)

• Space-efficient Euler partition and bipartite edge coloring
• Frameworks for designing in-place graph algorithms
• Space efficient algorithms for breadth-depth search
• Linear-time in-place DFS and BFS on the word RAM
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Fast breadth-first search in still less space
• Space efficient linear time algorithms for BFS, DFS and applications
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Space-efficient basic graph algorithms
• Biconnectivity, chain decomposition and st-numbering using O(n) bits
• A framework for in-place graph algorithms
• Optimal In-place Algorithms for Basic Graph Problems
• Simple 2f-Color Choice Dictionaries
• A constant-time colored choice dictionary with almost robust iteration
• Indexing graph search trees and applications
• Space-efficient biconnected components and recognition of outerplanar graphs
• Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
• Space-efficient graph coarsening with applications to succinct planar encodings

This page was built for publication: Improved space efficient algorithms for BFS, DFS and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817855)