ancestors algorithm, and Tarjan's strongly connected components algorithm, and he was one of five co-authors of the median of medians linear-time selection algorithm. The Hopcroft–Tarjan planarity testing algorithm was the first linear-time algorithm for planarity testing. Tarjan has also developed important data structures such as the Fibonacci heap (a heap data structure consisting of a forest of trees), and the splay tree (a self-adjusting binary search tree; co-invented by Tarjan and Daniel Sleator). Another significant contribution was the analysis of the disjoint-set data structure; he was the first to prove the optimal runtime involving the inverse Ackermann function. Awards Tarjan received the Turing Award jointly with John Hopcroft in 1986. The citation for the award states that it was: Tarjan was also elected an ACM Fellow in 1994. The citation for this award states: Some of the other awards for Tarjan include: Nevanlinna Prize in Information Science (1983) – first recipient Member of the American Academy of Arts and Sciences, elected 1985 National Academy of Sciences Award for Initiatives in Research (1984) Member of the National Academy of Sciences, elected 1987 Member of the National Academy of Engineering, elected 1988 Member of the American Philosophical Society, elected 1990 Paris Kanellakis Award in Theory and Practice, ACM (1999) Caltech Distinguished Alumni Award, California Institute of Technology (2010) Patents Tarjan holds at least 18 U.S. patents. These include: J. Bentley, D. Sleator, and R. E. Tarjan, U. S. Patent 4,796,003, Data Compaction, 1989 N. Mishra, R. Schreiber, and R. E. Tarjan, U. S. Patent 7,818,272, Method for discovery of clusters of objects in an arbitrary undirected graph using a difference between a fraction of internal connections and maximum fraction of connections by an outside object, 2010 B. Pinkas, S. Haber, R. E. Tarjan, and T. Sander, U. S. Patent 8220036, Establishing a secure channel with a human user, 2012 Notes References OCLC entries for Robert E Tarjan External links List of Robert Tarjan's patents on IPEXL's Patent Directory Robert Tarjan's home page at Princeton. 1948 births Living people Members of the United States National Academy of Sciences American computer scientists Theoretical computer scientists Turing Award laureates Nevanlinna Prize laureates Fellows of the Association for Computing Machinery Scientists at Bell Labs California Institute of Technology alumni Stanford University School of Engineering alumni Princeton University faculty People from Pomona, California 20th-century American Jews 21st-century American Jews Fellows of the Society for Industrial and Applied