Improved Space Efficient Algorithms for BFS, DFS and Applications
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, implementations of breadth first search (BFS) and
- PDF / 207,380 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 147 Views
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, implementations of breadth first search (BFS) and depth first search (DFS) in a graph on n vertices and m edges, taking O(m + n) time using O(n) and O(n lg lg n) bits of space respectively improving the naive O(n lg n)(We use lg to denote logarithm to the base 2.) bits implementation. 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 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 albeit with a slight increase in running time to O(m lg nf (n)) time where f (n) is any extremely slow growing function of n. These improve the space by a constant factor from earlier representations. We demonstrate the use of our data structure by developing another data structure using it that can represent a sequence nof n non-negative integers x1 , x2 , . . . xn using at most n i=1 xi +2n+o( i=1 xi +n) bits and, in constant time, determine whether the i-th element is 0 or decrement it otherwise. We use this data structure to output the vertices of a • directed acyclic graph in topological sorted order in O(m + n) time and O(m + n) bits, and • graph with degeneracy d in degeneracy order in O(nd) time using O(nd) bits. We also discuss an algorithm for finding a minimum weight spanning tree of a weighted undirected graph using at most n + o(n) bits. For DFS we give an O(m + n) bits implementation for finding a chain decomposition of a connected undirected graph, and to find cut vertices, bridges and maximal two connected subgraphs of a connected graph. We also provide a O(n) bits implementations for finding strongly connected components of a directed graph, to output the vertices of a directed acyclic graph in a topologically sorted manner, and to find a sparse biconnected subgraph of a biconnected graph. These improve the space required for earlier implementations from Ω(n lg n) bits. c Springer International Publishing Switzerland 2016 T.N. Dinh and M.T. Thai (Eds.): COCOON 2016, LNCS 9797, pp. 119–130, 2016. DOI: 10.1007/978-3-319-42634-1 10
120
1
N. Banerjee et al.
Introduction
Motivated by the rapid growth of huge data set (“big data”), algorithms that utilize space efficiently are becoming increasingly important than ever before. Another reason for the importance of space efficient algorithms is the proliferation of specialized handheld devices and embedded systems that have a limited supply of memory. Hence, there is a growing body of work that considers algorithms that do not modify
Data Loading...
