Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Pioneer

Robert Tarjan

Also Known As Robert Endre Tarjan · Robert E. Tarjan · R.E. Tarjan
Theory of Computation

Robert Endre Tarjan is an American computer scientist and mathematician, the discoverer of several graph theory algorithms including the strongly connected components algorithm, and co-inventor of splay trees and Fibonacci heaps. He and John Hopcroft won the 1986 ACM Turing Award. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Birth Year
1948 1
Birth Date
1948-04-30 1
Award
Paris Kanellakis Award 2
Award
Guggenheim Fellowship 2
Award
Frederick W. Lanchester Prize 2
Award
Turing Award 2
Award
ACM Fellow 2
Award
Fellow of the Society for Industrial and Applied Mathematics 2
Award
O'Reilly Open Source Award 2
Award
William O. Baker Award for Initiatives in Research 2
Award
IMU Abacus Medal 2
Contribution Kind
Algorithm 1
Highest Honour
Turing Award 1
Robert Tarjan
Filter Results1 entry

Tarjan's Strongly Connected Components Algorithm

Robert Tarjan
Connections

Associated With

John Hopcroft, Pioneers
Source Wikipedia: John Hopcroft

Credited

Median of medians, Algorithms
Source Median of medians (Wikipedia)
Splay Tree Algorithm, Algorithms
Source NIST Dictionary of Algorithms and Data Structures: splay tree
Tarjan's Strongly Connected Components Algorithm, Algorithms
Source Wikipedia: Tarjan's Strongly Connected Components Algorithm

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Robert Tarjan

Invented

Push-Relabel Algorithm, Algorithms

Robert Tarjan co-developed the push-relabel method for computing maximum flow with Andrew V. Goldberg, published in 1988.

Source Wikipedia: Robert Tarjan
Splay Tree Algorithm, Algorithms
Source NIST Dictionary of Algorithms and Data Structures: splay tree
Tarjan's Off-line Lowest Common Ancestors Algorithm, Algorithms

Robert Tarjan published this offline algorithm for computing the lowest common ancestors of paired nodes with Paul Gabow in 1979.

Source Wikipedia: Robert Tarjan
Tarjan's Strongly Connected Components Algorithm, Algorithms

Robert Tarjan published his linear-time algorithm for finding strongly connected components of a directed graph in 1972, based on depth-first search.

Source Wikipedia: Robert Tarjan
Topological Sort, Concepts

Robert Tarjan published a linear-time topological sort algorithm using depth-first search in his 1976 paper Edge-disjoint spanning trees and depth-first search, following Arthur Kahn's earlier 1962 algorithm.

Invented By

Median of medians, Algorithms
Source Median of medians (Wikipedia)

Long-Form Articles

From stargazer to data structure designer: the path of Robert Tarjan, Articles
In the Other Atlases

Same As

Robert Tarjan

Also in Mathematics Atlas: the same subject.

Is Discussed By

Turing Award

Also in Science Atlas: which discusses this subject.

Source Wikipedia: Robert Tarjantier 2

Nationality

United States

Also in Geography Atlas: the nationality of this subject.

Sources
1. Wikipedia: Robert Tarjan
Wikimedia Foundation
  • Lead section
    Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps.
  • Infobox, Born
    April 30, 1948
  • Lead paragraph
    He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps.
  • Infobox: awards
    Paris Kanellakis Award (1999) Turing Award (1986) Nevanlinna Prize (1982)
View the Source
2. Wikidata: Robert Tarjan
Wikidata Q92638, class allow-list match (w-wdresolver-0926)View the Source
Wikipedia: John Hopcroft
Wikimedia FoundationAssociated With: John Hopcroft, Career and honor section
Quote, Associated With: John Hopcroft, Career and honor section
In 1986 Hopcroft received the ACM Turing Award (jointly with Robert Tarjan) "for fundamental achievements in the design and analysis of algorithms and data structures."
View the Source
Median of medians (Wikipedia)
  • Credited: Median of medians, Lead, last paragraph
    sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan)
  • Invented By: Median of medians, Lead, last paragraph
    The algorithm was published in 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan).
View the Source
NIST Dictionary of Algorithms and Data Structures: splay tree
NIST Dictionary of Algorithms and Data Structures
  • Credited: Splay Tree Algorithm, References
    Daniel D. Sleator and Robert E. Tarjan , Self-Adjusting Binary Search Trees , Journal of the ACM, 32(3):652-686, 1985.
  • Invented: Splay Tree Algorithm, References
    Daniel D. Sleator and Robert E. Tarjan , Self-Adjusting Binary Search Trees , Journal of the ACM, 32(3):652-686, 1985.
View the Source
Wikipedia: Tarjan's Strongly Connected Components Algorithm
Wikimedia FoundationCredited: Tarjan's Strongly Connected Components Algorithm, Lead paragraph
Quote, Credited: Tarjan's Strongly Connected Components Algorithm, Lead paragraph
The algorithm is named for its inventor, Robert Tarjan.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.