Finding strong components using depth-first search

Robert E. Tarjan; Uri Zwick

doi:10.1016/j.ejc.2023.103815

Finding strong components using depth-first search

Robert E. Tarjan, Uri Zwick

Princeton University

Research output: Contribution to journal › Article › peer-review

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.

Original language	American English
Article number	103815
Journal	European Journal of Combinatorics
DOIs	https://doi.org/10.1016/j.ejc.2023.103815
State	Accepted/In press - 2023

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2023.103815

Cite this

@article{8ef008e958494d7da094a84842883f53,

title = "Finding strong components using depth-first search",

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.",

author = "Tarjan, {Robert E.} and Uri Zwick",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Ltd",

year = "2023",

doi = "10.1016/j.ejc.2023.103815",

language = "American English",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Finding strong components using depth-first search

AU - Tarjan, Robert E.

AU - Zwick, Uri

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85176096442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85176096442&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2023.103815

DO - 10.1016/j.ejc.2023.103815

M3 - Article

SN - 0195-6698

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103815

ER -

Finding strong components using depth-first search

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this