Linear Algebraic Depth-First Search
summary
Argues a concrete linear-algebra formulation for depth-first search that encodes the stack and frontier via row/column permutations on the adjacency matrix, maintains a three-region array (visited, partial, frontier), and applies the same permutation matrix left and right to advance state. Shows executable constructions for binary tree traversal, general graph traversal, and biconnected components, avoids duplicating stack entries, reports results as work-in-progress with plans to map to GraphBLAS/HPC kernels.
AI-written summary · about
chapters (10)
- 0:00Intro
- 2:04Cross Representation
- 3:25Example
- 6:15Approach
- 8:18Permutations
- 9:14Permutation Matrix
- 12:35General Graphs
- 15:14Summary
- 15:45Looking Forward
- 16:32Questions
related talks
30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...
59mWhat about Binary Search Trees?
14maDFS: An Almost Depth-First-Search Distributed Graph-Querying System
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
32mFrom Sparse Matrices to Graphs and Back Again
16mSpatial Programming for Environmental Monitoring
29mParallel Cluster-BFS and Applications to Shortest Paths