Optimal algebraic Breadth-First Search for sparse graphs

Understand

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods.

• An exemplar for these approaches is Breadth-First Search (BFS).
• The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the $n \times n$ adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance.
• Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods.