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
Connections

Associated With

John Hopcroft, Pioneers
Source Wikipedia: John Hopcroft

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

Invented By

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.

In the Other Atlases
Sources
1. Wikipedia: Robert Tarjan
Wikimedia Foundation
  • Lead section
    Robert Endre Tarjan 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
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
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.