Fast Breadth-First Search in Still Less Space
classification
💻 cs.DS
keywords
breadth-firstsearchbitscarrieddirectededgesfastgraph
read the original abstract
It is shown that a breadth-first search in a directed or undirected graph with $n$ vertices and $m$ edges can be carried out in $O(n+m)$ time with $n\log_2 3+O((\log n)^2)$ bits of working memory.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.