Robert Tarjan

Robert " Bob" Endre Tarjan ( born April 30, 1948 in Pomona, California ) is an American computer scientist. In 1986 he was honored along with John E. Hopcroft for the design and analysis of algorithms and data structures with the Turing Award.

He is a professor at Princeton University and works for the American company Hewlett -Packard.

According to him, different algorithms are named:

  • Algorithm of Tarjan for determining a minimum spanning tree
  • Algorithm of Hopcroft and Tarjan
  • Goldberg - Tarjan algorithm for determining a maximum st- flow

In addition, he also introduced the data structures Fibonacci heap and splay tree.

Life

Tarjan studied at Caltech in Pasadena, California, mathematics, and completed his undergraduate studies in 1969. He moved to Stanford University, where, in 1971 with a Masters in computer science in 1972 and his Ph.D. made in computer science with a minor in mathematics. His thesis An Efficient Planarity Algorithm was supervised by Robert Floyd, the lectures by Donald Ervin Knuth.

He then spent a year as a research associate at Cornell University, then for two years Miller Research Fellow at the University of California, Berkeley, and from 1974 to 1977 a research associate and then to 1980 associate professor of computer science at Stanford University. 1981 to 1985 he was adjunct professor at New York University. Since 1985 he is James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. From 1989 to 1994 and again since 2001, he is there also co-director of the National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science. In 1996 he was a visiting professor at MIT.

In parallel, he began in 1980 a career in the industry, was initially to 1989 Member of Technical Staff at AT & T Bell Laboratories, then to 1997, Fellow of the NEC Research Institute, and then to 2001 Chief Scientist of Intertrust Technologies. In 2002, he was briefly Corporate Fellow of Compaq, and was at its acquisition by Hewlett -Packard chief scientist there, from 2003 then Senior Fellow.

Under Tarjans 25 doctoral students are also the German Thomas Lengauer and Monika Henzinger.

Awards (selection)

Works

  • RE Tarjan: Data Structures and Algorithms Network. CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983. ISBN 0-89871-187-8
  • G. Polya, RE Tarjan, DR Woods: Notes on Introductory Combinatorics. Birkhäuser, Boston, MA, 1983
Hewlett-Packard Tarjan's strongly connected components algorithm Nevanlinna Prize American Academy of Arts and Sciences National Academy of Sciences National Academy of Engineering American Association for the Advancement of Science American Philosophical Society Association for Computing Machinery New York Academy of Sciences Alan Perlis Maurice Wilkes James H. Wilkinson John McCarthy (computer scientist) Charles Bachman Donald Knuth Allen Newell Herbert A. Simon Michael O. Rabin Kenneth E. Iverson Stephen Cook Niklaus Wirth Richard M. Karp John Cocke Manuel Blum Amir Pnueli Kristen Nygaard Ron Rivest Adi Shamir E. Allen Emerson Joseph Sifakis Charles P. Thacker Judea Pearl Leslie Lamport
135031
de