There is a recent push by a segment of the graph community to implement graph algorithms in the language of linear algebra. However, graph algorithms that depend on depth-first search techniques are often highlighted as limitations of the linear algebraic approach as there are no existing formulation of depth-first search graph algorithms expressed in the language of linear algebra. This paper provides a linear algebraic approach for developing depth-first search graph traversal algorithms and demonstrates its use for defining three classical DFS-based algorithms: Binary tree traversal, graph traversal, and biconnected components.
Sat 22 JunDisplayed time zone: Tijuana, Baja California change
11:30 - 12:30
|Finite Difference Methods Fengshui: Alignment through a Mathematics of Arrays
|Linear Algebraic Depth-First Search