Robert Endre Tarjan

Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, where he has been a faculty member since 1985. He maintains an active research program in theoretical computer science and algorithms despite being on leave status. His career spans multiple prestigious academic institutions and significant industry collaborations.

His educational background includes:

• B.S. in Mathematics from Caltech (1969)
• M.S. in Computer Science from Stanford University (1971)
• Ph.D. in Computer Science from Stanford University (1972)

Tarjan's research has fundamentally shaped theoretical computer science, particularly in graph algorithms and data structures. He pioneered the use of depth-first search techniques, developed amortized analysis for data structures, and created influential algorithms including union-find with path compression, splay trees, and Fibonacci heaps. His work bridges theoretical elegance with practical applications in network optimization and computational problems. The concepts he developed are now standard material in undergraduate algorithm courses worldwide.

Tarjan has received numerous prestigious honors:

• ACM Turing Award (1986) for fundamental achievements in algorithms and data structures
• First recipient of the Rolf Nevanlinna Prize (1983)
• Membership in the National Academy of Sciences (1987), National Academy of Engineering (1988), and American Philosophical Society (1990)
• SIAM Fellow (2009), ACM Fellow (1994), and American Academy of Arts & Sciences Fellow (1985)
• Caltech Distinguished Alumni Award (2010) and Blaise Pascal Medal (2004)

As an advisor, Tarjan has mentored notable computer scientists including Danny Sleator, Neal Sarnak, and Haim Kaplan. His industry collaborations have been extensive, with significant roles at AT&T Bell Laboratories (1980-1989), NEC Research Institute (1989-1997), InterTrust Technologies (1997-2001), Compaq/HP Research Labs (2002-2003), and Microsoft. These partnerships have translated theoretical advances into practical applications while securing research funding for his academic work. In March 2025, Tarjan was recognized with a lifetime achievement award from the International Congress of Basic Science for his outstanding contributions to theoretical computer science.

Tarjan's research laboratory has been a hub for theoretical computer science innovation, with particular focus on combinatorial algorithms. His approach emphasizes elegance and efficiency, seeking what he describes as algorithms from 'The Book' that records God's most elegant mathematical proofs and algorithms. His dynamic research group has consistently produced groundbreaking work that bridges theoretical insights with practical computational problems.