HackerPapers

arXiv:2201.07197cs.DS

Finding Strong Components Using Depth-First Search

Robert E. Tarjan, Uri Zwick

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
27 pages. In memory of Pierre Rosenstiehl. A slightly revised version
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Aug 2024 to Aug 2024.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. SIMD Matters: Graph Coloring 1 comment

    • 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…

      matt_dView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.