The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Robert Endre Tarjan

Born 30 April 1948, Pomona, California, USA

ACM A.M. Turing Award (1986) with John E. Hopcroft “for fundamental achievements in the design and analysis of algorithms and data structures.”

Robert Endre Tarjan earned his bachelor’s degree in Mathematics in 1969 at Caltech, the California Institute of Technology in Pasadena. Then, undecided initially between Mathematics and Computer Science, he opted for the latter, enjoying the ability to use his mathematical skills to solve problems in practical applications. At Stanford University, he took a Master’s in Computer Science (1971), and then his Ph.D. (1972), in Computer Science with a minor in Mathematics. Then Tarjan went as an assistant professor of Computer Science to Cornell University (1972-1973), as Miller Research Fellow to the University of California, Berkeley (1973-1975) and finally back to Stanford University, first as assistant professor of Computer Science (1974-1977), then as an associate professor (1977-1980). Following that he was an employee of AT&T Bell Laboratories in Murray Hill, New Jersey (1980-1989) and was at the same time an adjunct professor of Computer Science at New York University (1981-1985). Since 1985 he has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. After leaving AT&T Tarjan was a Fellow at the NEC Research Institute in Princeton (1989-1997), Chief Scientist at InterTrust Technologies in Sunnyvale, California (1997-2002), Senior Fellow at HP Labs in Palo Alto California (2002-2013), and currently a visiting researcher at MSR SVC.

Robert Endre Tarjan is a Fellow of the American Academy of Arts and Sciences (1985), and member of the National Academy of Sciences (1987) and the National Academy of Engineering (1988). He is the recipient of numerous awards, including the Nevanlinna Prize in Information Science (1983), the National Academy of Sciences Award for Initiatives in Research (1984), the ACM Paris Kanellakis Theory and Practice Award (1999) and the Blaise Pascal Medal for Mathematics and Computer Science of the European Academy of Sciences (2004).

Robert Endre Tarjan’s father, George Tarjan (1912-1991) was a well-known child psychiatrist who pioneered research into developmental disabilities. His mother Helen Tarjan (1918-2009) was a housewife. Tarjan has three daughters by his first marriage, Alice Tarjan, Zosia Zawacki, and Lily Tarjan. He is currently married to Nayla Rizk. He enjoys hiking, biking, and Sudoku. Robert Endre Tarjan is an inventor of algorithms, instructions with which computers can solve maths problems step by step. Tarjan’s algorithms usually concern graph-theoretical problems.

One can imagine graphs as something like street maps or pipe networks: nodes (pumping stations or cities) are connected by edges (pipes or roads). The study of graphs can provide answers in many areas of mathematics, because mathematical problems can often be translated into the language of graphs.

An interesting application is, for example, flow in directed graphs: virtual water flows through the pipes in the graph, and each pipe must be flushed in one direction only. Some nodes are sources, others sinks and the rest of the nodes serves as distributors: they direct the water from the incoming pipes to the outgoing pipes. If one then stipulates that there is one source and one drain, and that each tube can withstand no more than a certain flow rate, then there is a major problem: how much water can be sent through this pipe network? This problem of “maximum s-t-flow” is today usually solved with the Goldberg-Tarjan algorithm, developed by Tarjan together with Andrew Goldberg. It is fast in the mathematical sense, and therefore became a classic in graph theory. Using another of Tarjan’s algorithms, you can find ‘strong connected components’ in a directed graph, i. e. the parts of the graph where each node can be reached from any other node whilst obeying the direction of one-way streets. Also very well-known is Tarjan’s algorithm for finding ‘minimal spanning trees’, developed with David Karger and Philip Klein. This algorithm marks on a graph exactly those edges that you need to run from any node to any other node without ever running into a loop. If each edge on the graph has a price, then the algorithm chooses the set of edges with the lowest total cost.