Hacker News new | ask | show | jobs
by matt_d 667 days ago
For the particularly useful subgraph of topics, see "Notes on Graph Algorithms Used in Optimizing Compilers" by Carl Offner: http://www.cs.umb.edu/~offner/files/flow_graph.pdf

That, and pretty much anything (co)authored by Robert E. Tarjan. I'm serious: https://github.com/search?q=repo%3Allvm%2Fllvm-project%20tar...

There's a good recent survey of the three workhorses: "We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and (3) a bidirectional search algorithm."

Finding Strong Components Using Depth-First Search Robert E. Tarjan, Uri Zwick https://arxiv.org/abs/2201.07197