Robert Tarjan

Last updated
Robert Endre Tarjan
Bob Tarjan.jpg
Born (1948-04-30) April 30, 1948 (age 75)
Pomona, California
CitizenshipAmerican
Alma mater California Institute of Technology (BS)
Stanford University (MS, PhD)
Known forAlgorithms and data structures
Awards Paris Kanellakis Award (1999)
Turing Award (1986)
Nevanlinna Prize (1982)
Scientific career
Fields Computer science
Institutions Princeton University
New York University
Stanford University
University of California, Berkeley
Cornell University
Microsoft Research
Intertrust Technologies
Hewlett-Packard
Compaq
NEC Research
Bell Labs
Thesis An Efficient Planarity Algorithm  (1972)
Doctoral advisor Robert W. Floyd
Other academic advisors Donald Knuth
Doctoral students
Website www.cs.princeton.edu/~ret/

Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.

Contents

Personal life and education

He was born in Pomona, California. His father, raised in Hungary, [1] was a child psychiatrist, specializing in mental retardation, and ran a state hospital. [2] As a child, Tarjan read a lot of science fiction, and wanted to be an astronomer. He became interested in mathematics after reading Martin Gardner's mathematical games column in Scientific American. He became seriously interested in math in the eighth grade, thanks to a "very stimulating" teacher. [3]

While he was in high school, Tarjan got a job, where he worked with IBM punch card collators. He first worked with real computers while studying astronomy at the Summer Science Program in 1964. [2]

Tarjan obtained a Bachelor's degree in mathematics from the California Institute of Technology in 1969. At Stanford University, he received his master's degree in computer science in 1971 and a Ph.D. in computer science (with a minor in mathematics) in 1972. At Stanford, he was supervised by Robert Floyd [4] and Donald Knuth, [5] both highly prominent computer scientists, and his Ph.D. dissertation was An Efficient Planarity Algorithm. Tarjan selected computer science as his area of interest because he believed that computer science was a way of doing mathematics that could have a practical impact. [6]

Tarjan now lives in Princeton, NJ, and Silicon Valley. He is married to Nayla Rizk. [7] He has three daughters: Alice Tarjan, Sophie Zawacki, and Maxine Tarjan. [8]

Computer science career

Tarjan has been teaching at Princeton University since 1985. [6] He has also held academic positions at Cornell University (1972–73), University of California, Berkeley (1973–1975), Stanford University (1974–1980), and New York University (1981–1985). He has also been a fellow of the NEC Research Institute (1989–1997). [9] In April 2013 he joined Microsoft Research Silicon Valley in addition to the position at Princeton. In October 2014 he rejoined Intertrust Technologies as chief scientist.

Tarjan has worked at AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014–present), Compaq (2002) and Hewlett Packard (2006–2013).

Algorithms and data structures

Tarjan is known for his pioneering work on graph theory algorithms and data structures. Some of his well-known algorithms include Tarjan's off-line least common ancestors algorithm, Tarjan's strongly connected components algorithm, and Tarjan's bridge-finding 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. [10]

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. [11]

Awards

Tarjan received the Turing Award jointly with John Hopcroft in 1986. The citation for the award states [9] that it was:

For fundamental achievements in the design and analysis of algorithms and data structures.

Tarjan was also elected an ACM Fellow in 1994. The citation for this award states: [12]

For seminal advances in the design and analysis of data structures and algorithms.

Some of the other awards for Tarjan include:

Selected publications

Tarjan's papers have been collectively cited over 94,000 times. [19] Among the most cited are:

Patents

Tarjan holds at least 18 U.S. patents. [5] These include:

Notes

  1. ↑ "Jewish Recipients of the ACM A.M. Turing Award". jinfo.org.
  2. 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. "Robert E. Tarjan: In Search of Good Structure". Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists . Copernicus/Springer. pp.  102–119. ISBN   978-0-387-97992-2. OCLC   32240355.
  3. ↑ "Robert Tarjan: The Art of the Algorithm". Hewlett-Packard. Retrieved 2010-09-05.
  4. ↑ "Robert Endre Tarjan". Mathematics Genealogy Project. Retrieved 2008-01-09.
  5. 1 2 Tarjan, Robert Endre (November 15, 2019). "Curriculum Vitae" (PDF). Archived from the original (PDF) on 2019-11-23. Retrieved 2019-11-23.
  6. 1 2 "Robert Endre Tarjan: The art of the algorithm (interview)". Hewlett-Packard. September 2004. Retrieved 2008-01-09.
  7. ↑ "Nayla Rizk and Robert Tarjan". The New York Times. July 2013.
  8. ↑ "Photos from Bob Tarjan's 60th Birthday Symposium". DIMACS. May 2008.
  9. 1 2 3 4 5 King, V. "Robert E Tarjan — A.M. Turing Award Laureate". ACM . Retrieved 2014-01-19.
  10. ↑ Kocay, William; Kreher, Donald L (2005). "Planar Graphs". Graphs, algorithms, and optimization . Boca Raton: Chapman & Hall/CRC. p.  312. ISBN   978-1-58488-396-8. OCLC   56319851.
  11. ↑ Tarjan, Robert E.; van Leeuwen, Jan (1984). "Worst-case analysis of set union algorithms". Journal of the ACM . 31 (2): 245–281. doi: 10.1145/62.2160 . S2CID   5363073.
  12. ↑ "Fellows Award — Robert E. Tarjan". ACM. September 25, 1998. Retrieved 2005-11-18.
  13. ↑ "Rolf Nevanlinna Prize Winners". International Mathematical Union. Archived from the original on 2008-12-27. Retrieved 2014-01-19.
  14. ↑ "Robert Endre Tarjan". American Academy of Arts & Sciences. Retrieved 2020-06-15.
  15. ↑ "Robert Tarjan". www.nasonline.org. Retrieved 2020-06-15.
  16. ↑ "Dr. Robert E. Tarjan". NAE Website. Retrieved 2020-06-15.
  17. ↑ "APS Member History". search.amphilsoc.org. Retrieved 2022-04-19.
  18. ↑ "Caltech Names Five Distinguished Alumni" (Press release). California Institute of Technology. 2010-03-15. Archived from the original on 2010-10-10. Retrieved 2010-08-26.
  19. ↑ "Robert Tarjan Google Scholar Page". Google Scholar. Retrieved 6 March 2023.
  20. ↑ Tarjan, Robert (1972-06-01). "Depth-First Search and Linear Graph Algorithms". SIAM Journal on Computing. 1 (2): 146–160. doi:10.1137/0201010. ISSN   0097-5397. S2CID   16467262.
  21. ↑ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM. 34 (3): 596–615. doi: 10.1145/28869.28874 . ISSN   0004-5411. S2CID   7904683.
  22. ↑ "Back Matter". Data Structures and Network Algorithms: 125–131. January 1983. doi:10.1137/1.9781611970265.bm. ISBN   978-0-89871-187-5.
  23. ↑ Goldberg, Andrew V.; Tarjan, Robert E. (1988-10-01). "A new approach to the maximum-flow problem". Journal of the ACM. 35 (4): 921–940. doi: 10.1145/48014.61051 . ISSN   0004-5411. S2CID   14492800.
  24. ↑ Bentley, Jon L.; Sleator, Daniel D. K.; Tarjan, Robert E. (January 3, 1989). "United States Patent 4796003 — Data compaction".
  25. ↑ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (October 19, 2010). "United States Patent 7818272 — 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".
  26. ↑ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (July 10, 2012). "United States Patent 8220036 — Establishing a secure channel with a human user".

Related Research Articles

<span class="mw-page-title-main">Dijkstra's algorithm</span> Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Daniel Dominic Kaplan Sleator is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award for the splay tree data structure.

<span class="mw-page-title-main">Robert Sedgewick (computer scientist)</span> American computer scientist

Robert Sedgewick is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University and was a member of the board of directors of Adobe Systems (1990–2016). He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA. His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing college curriculums in computer science.

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

<span class="mw-page-title-main">John Hopcroft</span> American computer scientist (born 1939)

John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University, Co-Director of the Center on Frontiers of Computing Studies at Peking University, and the Director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations :

Prof. Athanasios K. Tsakalidis is a Greek computer scientist, a professor at the Graphics, Multimedia and GIS Laboratory, Computer Engineering and Informatics Department (CEID), University of Patras, Greece.

<span class="mw-page-title-main">Left-child right-sibling binary tree</span>

Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain.

A program structure tree (PST) is a hierarchical diagram that displays the nesting relationship of single-entry single-exit (SESE) fragments/regions, showing the organization of a computer program. Nodes in this tree represent SESE regions of the program, while edges represent nesting regions. The PST is defined for all control flow graphs.

<span class="mw-page-title-main">Kurt Mehlhorn</span> German computer scientist (born 1949)

Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: for insertion, find-minimum, meld and decrease-key and for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.

NEC Laboratories America, Inc. , formerly known as NEC Research Institute, is the US-based center for NEC Corporation’s global network of corporate research laboratories. It was established in 1988 with the primary location in Princeton, New Jersey and subsequently, a second location in the San Francisco Bay Area, specifically San Jose, California. The lab is a subsidiary of the NEC Corporation of America, headquartered in Irving, Texas. Its mission is to generate significant new knowledge and create innovative solutions for society in collaboration with industry, academia, and governments. Most research results from NEC Labs America are published in the open scientific literature.

In combinatorial mathematics and theoretical computer science, heavy-light decomposition is a technique for decomposing a rooted tree into a set of paths. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants. The selected edges form the paths of the decomposition.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

Jean Vuillemin is a French computer scientist known for his work in data structures and parallel computing. He is a professor of computer science at the École normale supérieure (Paris).

<span class="mw-page-title-main">Philip N. Klein</span> American computer scientist

Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs. 

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.