Title/Position
James S. McDonnell Distinguished University Professor

Degree
Ph.D., Stanford University, 1972

ret(@cs.princeton.edu) (609) 258-4797 305 Computer Science

Homepage
https://www.cs.princeton.edu/~ret

Research

Interests: Data structures; graph algorithms; combinatorial optimization; computational complexity; computational geometry; parallel algorithms.
ACM Turing Award, 1986. Fellow Amer. Acad. Arts & Sci. 1985; Member Nat. Acad. Sci. 1987; Member Nat. Acad. Engineering 1988; Member Amer. Phil. Soc. 1990; ACM Fellow 1994; SIAM Fellow 2009.
Research Areas: Theory

Short Bio

Robert E. Tarjan, the James S. McDonnell Distinguished University Professor of Computer Science, joined Princeton in 1985. He received doctoral and master’s degrees in computer science from Stanford in 1972 and 1971, respectively, after earning a bachelor’s in mathematics from Caltech. His academic experience involved assistant professorships at Cornell and Stanford, and a Miller research fellowship at UC, Berkeley. Professor Tarjan’s extensive involvement in the private sector includes past and continuing fellowship, research and scientific roles at the NEC Research Institute, Princeton; InterTrust Technologies, Sunnyvale, CA; Compaq Computer, Houston, TX; Hewlett-Packard, Palo Alto, CA; and Microsoft, Mountain View, CA. His honors include Caltech’s Distinguished Alumni Award in 2010, the 2009 Edelman Award from INFORMS (member of winning H-P team), fellow of the Society for Industrial and Applied Mathematics (2009), and the Blaise Pascal Medal in Mathematics and Computer Science from the European Academy of Sciences in 2004. Professor Tarjan was the first winner of the Rolf Nevanlinna Prize, established in 1982 and awarded every four years for outstanding contributions in mathematical aspects of information sciences by the International Mathematical Union.

Selected Publications

“Data Structures and Network Algorithms.” R. E. Tarjan. CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983. (Book)
“Notes on Introductory Combinatorics.” G. Polya, R. E. Tarjan, D. R. Woods. Birkh?user, Boston, MA, 1983. (Book)
“Depth-first search and linear graph algorithms.” R. E. Tarjan. SIAM Journal on Computing 1 (1972), pp. 146-160; preliminary version in Conf. Record Twelfth Annual Symp. on Switching and Automata Theory (1971), pp. 114-121.
“Fibonacci heaps and their uses in improved network optimization algorithms,” M. L. Fredman and R. E. Tarjan. J. Assoc. Comput. Mach. 34 (1987), pp. 596-615; preliminary version in Proc. 25th Annual IEEE Symp. on Found. of Comp. Sci. (1984), pp. 338-346.
“Amortized efficiency of list update and paging rules.” D. D. Sleator and R. E. Tarjan. Comm. ACM 28 (1985), pp. 202-208.