Tarjan's strongly connected components algorithm
E323102
depth-first search based algorithm
graph algorithm
linear-time algorithm
strongly connected components algorithm
Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
All labels observed (3)
| Label | Occurrences |
|---|---|
| Tarjan's SCC algorithm | 1 |
| Tarjan's algorithm for strongly connected components | 1 |
| Tarjan's strongly connected components algorithm canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T3043276 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Tarjan's strongly connected components algorithm Context triple: [Robert Tarjan, notableConcept, Tarjan's strongly connected components algorithm]
-
A.
union–find data structure
The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
-
B.
Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
-
C.
Huet unification algorithm
The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
-
D.
Robert Tarjan
Robert Tarjan is an American computer scientist renowned for his pioneering work in algorithms and data structures, including the development of efficient graph algorithms and the union–find data structure.
-
E.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Tarjan's strongly connected components algorithm Target entity description: Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
-
A.
union–find data structure
The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
-
B.
Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
-
C.
Huet unification algorithm
The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
-
D.
Robert Tarjan
Robert Tarjan is an American computer scientist renowned for his pioneering work in algorithms and data structures, including the development of efficient graph algorithms and the union–find data structure.
-
E.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
- F. None of above. chosen
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
depth-first search based algorithm
ⓘ
graph algorithm ⓘ linear-time algorithm ⓘ strongly connected components algorithm ⓘ |
| advantageOver | Kosaraju's algorithm in using a single depth-first search pass ⓘ |
| alsoKnownAs |
Tarjan's strongly connected components algorithm
ⓘ
surface form:
Tarjan's SCC algorithm
|
| assumes | finite directed graph ⓘ |
| category |
graph decomposition algorithm
ⓘ
single-source DFS-based algorithm ⓘ |
| complexityClass | linear in the size of the graph ⓘ |
| correctnessBasedOn |
definition of strongly connected components
ⓘ
properties of depth-first search trees in directed graphs ⓘ |
| field |
algorithms
ⓘ
computer science ⓘ graph theory ⓘ |
| guarantees |
components are reported in reverse topological order of the component graph
ⓘ
each vertex belongs to exactly one strongly connected component ⓘ |
| implementationDetail |
each edge is examined exactly once
ⓘ
each vertex is pushed onto the stack at most once ⓘ |
| input | directed graph ⓘ |
| introducedBy | Robert Tarjan ⓘ |
| introducedIn | 1972 ⓘ |
| namedAfter | Robert Tarjan ⓘ |
| output | partition of vertices into strongly connected components ⓘ |
| property | online with respect to DFS order of components ⓘ |
| publishedIn | SIAM Journal on Computing ⓘ |
| relatedTo |
Gabow's strongly connected components algorithm
ⓘ
Kosaraju's algorithm ⓘ |
| requires | graph stored in adjacency representation ⓘ |
| solvesProblem | finding strongly connected components in a directed graph ⓘ |
| spaceComplexity | O(V) ⓘ |
| step |
identify root vertices where index equals low-link value
ⓘ
maintain a stack of active vertices in the current DFS search path ⓘ perform depth-first search assigning an index to each visited vertex ⓘ pop vertices from the stack to form a strongly connected component when a root is found ⓘ update low-link values based on DFS tree edges and back edges ⓘ |
| timeComplexity | O(V + E) ⓘ |
| usedIn |
circuit analysis
ⓘ
deadlock detection ⓘ decomposition of graphs into strongly connected components ⓘ model checking ⓘ program analysis ⓘ |
| usesConcept | low-link values ⓘ |
| usesDataStructure |
arrays for indices and low-link values
ⓘ
stack ⓘ |
| usesTechnique | depth-first search ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Tarjan's strongly connected components algorithm Description of subject: Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Tarjan's algorithm for strongly connected components
Tarjan's strongly connected components algorithm
→
alsoKnownAs
→
Tarjan's strongly connected components algorithm
ⓘ
this entity surface form:
Tarjan's SCC algorithm