Tag
graph-traversal
- Apr 18, 2026 Iterative Depth-First Search Without Losing Finish Times Why a stack of vertices does not reproduce recursive DFS, how to keep an explicit frame with a resume index, and what changes when the traversal can be paused and resumed. algorithms
- Jun 13, 2025 Labelling Connected Components Once Versus Maintaining Them Under Insertions How a single traversal assigns component identifiers in linear time, why the same problem becomes hard when edges arrive online, and what the two approaches cost on either side of that line. algorithms
- May 17, 2025 Discovery and Finish Times: What DFS Edge Classification Encodes How the two timestamps recorded by depth-first search partition a directed graph into tree, back, forward, and cross edges, and why undirected graphs admit only two of those classes. algorithms
- May 8, 2025 Two-Colouring a Graph: Why BFS Decides Bipartiteness and Odd Cycles Do Not The equivalence between bipartite graphs and odd-cycle-free graphs, how a colouring traversal detects the failure in linear time, and what the check does not decide. algorithms
- Mar 29, 2025 Disk-Resident Graph Indexes and the Memory Bandwidth Wall What changes when the vector index no longer fits in RAM: page-oriented adjacency storage, the cost of a random read per hop, and why compression and caching decide throughput. information retrieval
- Apr 8, 2024 Why Breadth-First Search Cannot Discover Vertices Out of Distance Order The queue invariant behind BFS distances, why vertices must be marked on enqueue rather than on dequeue, and where the layer argument stops holding. algorithms
- Dec 15, 2022 Building the Dependency Graph from Manifests Why a manifest describes requirements rather than edges, how node identity is decided, which dependency kinds the walk follows, and why the graph only exists after versions are chosen. developer tools