Reproduce “Improved Space efficient linear time algorithms for BFS, DFS and applications” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman, Srinivasa Rao Satti
The authors present a breadth-first search (BFS) method that traverses directed or undirected graphs without storing the usual queue of vertex identifiers. By processing vertices from alternating sets for consecutive distance levels, the method uses O(m+n) time and at most 2n+o(n) workspace bits. This bound excludes the read-only input and write-only output; the paper reports theoretical bounds, not benchmark results.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.