Computer Science > Data Structures and Algorithms
[Submitted on 19 Jun 2019]
Title:Space Efficient Algorithms for Breadth-Depth Search
View PDFAbstract:Continuing the recent trend, in this article we design several space-efficient algorithms for two well-known graph search methods. Both these search methods share the same name {\it breadth-depth search} (henceforth {\sf BDS}), although they work entirely in different fashion. The classical implementation for these graph search methods takes $O(m+n)$ time and $O(n \lg n)$ bits of space in the standard word RAM model (with word size being $\Theta(\lg n)$ bits), where $m$ and $n$ denotes the number of edges and vertices of the input graph respectively. Our goal here is to beat the space bound of the classical implementations, and design $o(n \lg n)$ space algorithms for these search methods by paying little to no penalty in the running time. Note that our space bounds (i.e., with $o(n \lg n)$ bits of space) do not even allow us to explicitly store the required information to implement the classical algorithms, yet our algorithms visits and reports all the vertices of the input graph in correct order.
Submission history
From: Sankardeep Chakraborty [view email][v1] Wed, 19 Jun 2019 01:45:10 UTC (53 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.