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
Robert Tarjan
Filter Results1 entry

Topological Sort

Robert Tarjan
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
Robert Tarjan (Wikidata)
  • Wikidata alias: Robert Endre Tarjan
    Robert Endre Tarjan
  • Wikidata P166: Paris Kanellakis Award
    Wikidata P166 (award received): Paris Kanellakis Award.
  • Wikidata P166: Guggenheim Fellowship
    Wikidata P166 (award received): Guggenheim Fellowship.
  • Wikidata P166: Frederick W. Lanchester Prize
    Wikidata P166 (award received): Frederick W. Lanchester Prize.
  • Wikidata P166: Turing Award
    Wikidata P166 (award received): Turing Award.
  • Wikidata P166: ACM Fellow
    Wikidata P166 (award received): ACM Fellow.
  • Wikidata P166: Fellow of the Society for Industrial and Applied Mathematics
    Wikidata P166 (award received): Fellow of the Society for Industrial and Applied Mathematics.
  • Wikidata P166: O'Reilly Open Source Award
    Wikidata P166 (award received): O'Reilly Open Source Award.
  • Wikidata P166: William O. Baker Award for Initiatives in Research
    Wikidata P166 (award received): William O. Baker Award for Initiatives in Research.
  • Wikidata P166: IMU Abacus Medal
    Wikidata P166 (award received): IMU Abacus Medal.
  • Wikidata alias: Robert E. Tarjan
    Robert E. Tarjan
  • Wikidata alias: R.E. Tarjan
    R.E. Tarjan
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.