Robert Tarjan
USABiography of Robert Tarjan
Robert Tarjan is a renowned American scientist in the field of computer systems theory. He is the author of numerous algorithms for solving problems in graph theory and discrete mathematics, including the Tarjan's off-line least common ancestors algorithm. He is also a co-author of data structures such as the Fibonacci heap and the splay tree.
Early Life and Education
Robert Tarjan's father was a pediatrician specializing in developmental delays and served as the director of the state's central polyclinic. In his childhood, Tarjan read a lot of science fiction and aspired to become an astronomer. However, his interest in mathematics grew after reading Martin Gardner's notes on mathematical games in Scientific American. His passion for mathematics was further nurtured by an "extremely motivating" teacher in the eighth grade. While in school, Tarjan had the opportunity to work with an IBM sorting machine for punched cards. In the summer school of 1964, he gained his first significant experience working with real computers.
Tarjan received his Bachelor's degree in Mathematics from the California Institute of Technology in 1969. He went on to obtain a Master's degree in Computer Science (1971) and a Doctor of Philosophy degree in Computer Science (1972) from Stanford University. His advisors at Stanford were Robert W. Floyd and Donald E. Knuth. Tarjan chose computer science as a path where mathematics could have tangible practical benefits.
Professional Career
Tarjan has served as a faculty member at Princeton University since 1985. He has also held academic positions at Cornell University (1972-1973), University of California, Berkeley (1973-1975), Stanford University (1974-1980), and New York University (1981-1985). He was a member of the NEC Research Institute from 1989 to 1997 and held a position as a Visiting Scientist at the University of Massachusetts in 1996. Tarjan worked at AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002), and currently at Hewlett Packard since 2006. He has been elected as a member of various ACM and IEEE committees and has served as an editor for several refereed journals. Tarjan has devised numerous efficient algorithms and data structures for solving various applied problems, publishing over 228 articles in refereed journals and monographs.
Contributions and Awards
Tarjan is well-known for his groundbreaking work in graph algorithms. Some of his notable contributions include the Tarjan's off-line least common ancestors algorithm for fast multiple searches of the deepest node in a tree that is the common ancestor of two given nodes, and the Tarjan's algorithm for strongly connected components. The Hopcroft-Tarjan algorithm was the first linear-time algorithm for planarity testing of graphs. Tarjan has developed several important data structures, including the Fibonacci heap and the splay tree (co-authored with Daniel Sleator).
Today, Robert Tarjan is a James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and also works at Hewlett-Packard. He received the Turing Award jointly with John Hopcroft in 1986 for "fundamental achievements in the design and analysis of algorithms and data structures." Tarjan was elected as an ACM Fellow in 1994 for his "productive work in the development and analysis of algorithms and data structures." He has also received various other awards, including the Nevanlinna Prize in 1982, the National Academy of Sciences Award for Initiatives in Research in 1984, the Paris Kanellakis Award in Theory and Practice from ACM in 1999, and the Blaise Pascal Medal in Mathematics and Computer Science from the European Academy of Sciences in 2004.
In late February 2009, Tarjan ranked 39th on the list of most cited authors in the CiteSeer project.
