معرفی
Robert E. Tarjan is a James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, where he has been since 1985. His career spans roles at Cornell University, Stanford University, AT&T Bell Laboratories, and industry positions at NEC Research Institute, Intertrust, and HP Labs. He earned his B.S. in Mathematics from Caltech (1969), M.S. (1971) and Ph.D. (1972) in Computer Science from Stanford University.
- B.S., Mathematics, California Institute of Technology (1969)
- M.S., Computer Science, Stanford University (1971)
- Ph.D., Computer Science (minor in Mathematics), Stanford University (1972)
Tarjan's research focuses on the design and analysis of algorithms and data structures, particularly for graph problems, network flows, and combinatorial optimization. He pioneered amortized analysis, introduced depth-first search techniques, and developed foundational structures like splay trees and Fibonacci heaps. His work on competitive analysis for online algorithms and persistent data structures has shaped modern algorithmic theory.
Tarjan has received numerous accolades including the Turing Award (1986), Nevanlinna Prize (1983), and the Paris Kanellakis Award (1999). He is a Fellow of ACM, AAAS, and SIAM, and a member of the National Academies of Science and Engineering.
- Collaborated with John Hopcroft on graph algorithms and planarity testing
- Developed the union-find data structure with path compression
- Invented splay trees and Fibonacci heaps
- Co-founded competitive analysis for online algorithms
- Authored over 250 papers and 15 patents
- Mentored students like Danny Sleator, Neal Sarnak, and Haim Kaplan
