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.
Fast Breadth-First Search in Still Less Space
Related papers
- Space Efficient Algorithms for Breadth-Depth Search (2019)β
- Nearly Optimal Space Efficient Algorithm for Depth First Search (2018)β
- Space-Efficient DFS and Applications: Simpler, Leaner, Faster (2018)β
- Indexing Graph Search Trees and Applications (2019)β
- Linear-Time In-Place DFS and BFS on the Word RAM (2019)β
- Frameworks for Designing In-place Graph Algorithms (2017)β
- Nearly Work-Efficient Parallel DFS in Undirected Graphs (2023)β
- Efficient Semi-External Breadth-First Search (2025)β