Editing Robert Tarjan

{{Short description|American computer scientist and mathematician}}
{{Infobox scientist
| image             = Bob Tarjan.jpg
| birth_name        = Robert Endre Tarjan
| birth_date        = {{Birth date and age|1948|4|30|mf=y}}
| birth_place       = [[Pomona, California|Pomona]], [[California]], U.S.
| death_date        = 
| death_place       = 
| fields            = [[Computer science]]
| workplaces        = [[Princeton University]]<br>[[New York University]]<br>[[Stanford University]]<br>[[University of California, Berkeley]]<br>[[Cornell University]]<br>[[Microsoft Research]]<br>[[Intertrust Technologies Corporation|Intertrust Technologies]]<br>[[Hewlett-Packard]]<br>[[Compaq]]<br>[[NEC Corporation of America|NEC Research]]<br>[[Bell Labs]]
| patrons           =
| education         = [[California Institute of Technology]] ([[Bachelor of Science|BS]])<br>[[Stanford University]] ([[Master of Science|MS]], [[Doctor of Philosophy|PhD]])
| thesis_title      = An Efficient Planarity Algorithm
| thesis_url        = https://dl.acm.org/citation.cfm?id=906252
| thesis_year       = 1972
| doctoral_advisor  = [[Robert W. Floyd]]
| academic_advisors = [[Donald Knuth]]
| doctoral_students = {{Plainlist|
*[[Thomas Lengauer]]
*[[Monika Henzinger]]
*[[Ramesh Sitaraman]]
*[[Daniel Sleator]]
*[[Jeff Westbrook]]
}}
| notable_students  = 
| known_for         = Algorithms and data structures
| influences        = 
| influenced        = 
| awards            = [[Paris Kanellakis Award]] (1999)<br>[[Turing Award]] (1986)<br>[[Nevanlinna Prize]] (1982)
| spouse            = <!--(or | spouses = )-->
| partner           = <!--(or | partners = )-->
| children          =
| signature         = <!--(filename only)-->
| signature_alt     =
| website           = {{URL|www.cs.princeton.edu/~ret/}}
| footnotes         =
}}
'''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 [[Tarjan's strongly connected components algorithm|strongly connected components algorithm]], and co-inventor of both [[splay tree]]s and [[Fibonacci heap]]s. Tarjan is currently the [[James S. McDonnell]] Distinguished University Professor of Computer Science at [[Princeton University]].

==Personal life and education==
He was born in [[Pomona, California]]. His father, George Tarjan (1912–1991), raised in Hungary,<ref>{{cite web|title=Jewish Recipients of the ACM A.M. Turing Award|website=jinfo.org|url=http://www.jinfo.org/Computer_ACM_Turing.html}}</ref> was a child psychiatrist, specializing in mental retardation, and ran a state hospital.<ref name="Out_of_Their_Minds">{{cite book
 | last = Shasha
 | first = Dennis Elliott
 | author2 = Lazere, Cathy A.
 | title = Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists
 | publisher = Copernicus/Springer
 | orig-year = 1995
 | year = 1998
 | isbn = 978-0-387-97992-2
 | oclc = 32240355
 | chapter = Robert E. Tarjan: In Search of Good Structure
 | pages = [https://archive.org/details/isbn_9780387979922/page/102 102–119]
 | url-access = registration
 | url = https://archive.org/details/isbn_9780387979922/page/102
 }}</ref> Robert Tarjan's [[James Tarjan|younger brother James]] became a chess grandmaster.<ref>{{cite journal|last=Melvin|first=Shabsin|title=George Tarjan, M.D. one hundred twelfth president, 1983-1984|journal=The American Journal of Psychiatry|volume=141|issue=8|pages=931–934|date=August 1984|doi=10.1176/ajp.141.8.931|pmid=6380318 }}</ref> As a child, Robert 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.<ref>{{cite web
 | url = http://www.hpl.hp.com/news/2004/oct_dec/tarjan.html
 | title = Robert Tarjan: The Art of the Algorithm
 | publisher = Hewlett-Packard
 | access-date = 2010-09-05
}}</ref>

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.<ref name="Out_of_Their_Minds"/>

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 [[Doctor of Philosophy|Ph.D.]] in computer science (with a minor in mathematics) in 1972. At Stanford, he was supervised by [[Robert W. Floyd|Robert Floyd]]<ref>{{cite web
 | url = http://genealogy.math.ndsu.nodak.edu/id.php?id=53460
 | title = Robert Endre Tarjan
 | publisher = Mathematics Genealogy Project
 | access-date = 2008-01-09
}}</ref> and [[Donald Knuth]],<ref name="CV"/> 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.<ref name="HP_art_of_algo">{{cite web
 | url = http://www.hpl.hp.com/news/2004/oct_dec/tarjan.html
 | title = Robert Endre Tarjan: The art of the algorithm (interview)
 |date=September 2004
 | publisher = Hewlett-Packard
 | access-date = 2008-01-09
}}</ref>

Tarjan now lives in Princeton, NJ, and Silicon Valley. He is married to Nayla Rizk.<ref>{{cite web
 | url = https://www.nytimes.com/2013/07/07/fashion/weddings/nayla-rizk-and-robert-tarjan.html
 | title = Nayla Rizk and Robert Tarjan
 | date = July 2013
 | work = The New York Times
}}</ref>
He has three daughters: Alice Tarjan, Sophie Zawacki, and Maxine Tarjan.<ref>{{cite web
 | url = http://dimacs.rutgers.edu/archive/Workshops/Tarjan/materials/event-photos.html
 | title = Photos from Bob Tarjan's 60th Birthday Symposium
 | date = May 2008
 | publisher = DIMACS
}}</ref>

==Computer science career==
Tarjan has been teaching at Princeton University since 1985.<ref name="HP_art_of_algo"/> 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).<ref name="turing"/> 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 [[Bridge (graph theory)#Tarjan's bridge-finding algorithm|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.<ref>{{cite book
 | last = Kocay
 | first = William
 |author2=Kreher, Donald L
  | title = Graphs, algorithms, and optimization
 | url = https://archive.org/details/graphsalgorithms00will
 | url-access = limited
 | publisher = Chapman & Hall/CRC
 | location = Boca Raton
 | year = 2005
 | isbn = 978-1-58488-396-8
 | oclc = 56319851
 | chapter = Planar Graphs
 | page = [https://archive.org/details/graphsalgorithms00will/page/n196 312]
}}</ref>

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]].<ref name="Tarjan1984">{{cite journal |first1=Robert E. |last1=Tarjan |author1-link=Robert E. Tarjan |first2=Jan |last2=van Leeuwen |author2-link=Jan van Leeuwen |title=Worst-case analysis of set union algorithms |journal=[[Journal of the ACM]] |volume=31 |issue=2 |pages=245–281 |year=1984 |doi= 10.1145/62.2160|s2cid=5363073 |doi-access=free }}</ref>

==Awards==
Tarjan received the [[Turing Award]] jointly with [[John Hopcroft]] in 1986.  The citation for the award states<ref name="turing">{{cite web|url=http://amturing.acm.org/award_winners/tarjan_1092048.cfm|title=Robert E Tarjan — A.M. Turing Award Laureate|first=V.|last=King|publisher=[[Association for Computing Machinery|ACM]]|access-date=2014-01-19}}</ref> that it was:

{{blockquote|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:<ref>{{cite web|url=http://www.acm.org/awards/fellows_citations_n-z/tarjan.html|title=Fellows Award — Robert E. Tarjan|date=September 25, 1998|publisher=[[Association for Computing Machinery|ACM]]|access-date=2005-11-18}}</ref>

{{blockquote|For seminal advances in the design and analysis of data structures and algorithms.}}

Some of the other awards for Tarjan include:
* [[Nevanlinna Prize]] in Information Science (1983)<ref name="turing"/> – first recipient<ref>{{cite web|url=http://www.mathunion.org/general/prizes/nevanlinna/prize-winners/|title=Rolf Nevanlinna Prize Winners|archive-url=https://web.archive.org/web/20081227210921/http://www.mathunion.org/general/prizes/nevanlinna/prize-winners/|archive-date=2008-12-27|publisher=[[International Mathematical Union]]|access-date=2014-01-19}}</ref>
*Member of the [[American Academy of Arts and Sciences]], elected 1985<ref>{{Cite web|title=Robert Endre Tarjan|url=https://www.amacad.org/person/robert-endre-tarjan|access-date=2020-06-15|website=American Academy of Arts & Sciences|language=en}}</ref>
* [[NAS Award for Initiatives in Research|National Academy of Sciences Award for Initiatives in Research]] (1984)<ref name="turing"/>
*Member of the [[National Academy of Sciences]], elected 1987<ref>{{Cite web|title=Robert Tarjan|url=http://www.nasonline.org/member-directory/members/15504.html|access-date=2020-06-15|website=www.nasonline.org}}</ref>
*Member of the [[National Academy of Engineering]], elected 1988<ref>{{Cite web|title=Dr. Robert E. Tarjan|url=https://nae.edu/27800/Dr-Robert-E-Tarjan|access-date=2020-06-15|website=NAE Website}}</ref>
*Member of the [[American Philosophical Society]], elected 1990<ref>{{Cite web |title=APS Member History |url=https://search.amphilsoc.org/memhist/search?creator=John+L.+Heilbron&title=&subject=&subdiv=&mem=&year=&year-max=&dead=&keyword=&smode=advanced |access-date=2022-04-19 |website=search.amphilsoc.org}}</ref>
* [[Paris Kanellakis Award]] in Theory and Practice, [[Association for Computing Machinery|ACM]] (1999)<ref name="turing"/>
* Caltech Distinguished Alumni Award, [[California Institute of Technology]] (2010)<ref>{{cite press release |url=http://media.caltech.edu/press_releases/13332 |title=Caltech Names Five Distinguished Alumni |date=2010-03-15 |publisher=[[California Institute of Technology]] |access-date=2010-08-26 |url-status=dead |archive-url=https://web.archive.org/web/20101010023119/http://media.caltech.edu/press_releases/13332 |archive-date=2010-10-10 }}</ref>

==Selected publications==

Tarjan's papers have been collectively cited over 94,000 times.<ref>{{cite web |title=Robert Tarjan Google Scholar Page |url=https://scholar.google.com/citations?user=lazJixIAAAAJ&hl=en&oi=ao |website=Google Scholar |access-date=6 March 2023}}</ref>  Among the most cited are:

* 1972: Depth-first search and linear graph algorithms, R Tarjan, [[SIAM Journal on Computing]] 1 (2), 146-160<ref>{{Cite journal|last=Tarjan|first=Robert|date=1972-06-01|title=Depth-First Search and Linear Graph Algorithms|url=https://epubs.siam.org/doi/abs/10.1137/0201010|journal=SIAM Journal on Computing|volume=1|issue=2|pages=146–160|doi=10.1137/0201010|s2cid=16467262 |issn=0097-5397}}</ref>
*1987: Fibonacci heaps and their uses in improved network optimization algorithms, ML Fredman, RE Tarjan, Journal of the ACM (JACM) 34 (3), 596-615<ref>{{Cite journal|last1=Fredman|first1=Michael L.|last2=Tarjan|first2=Robert Endre|date=1987-07-01|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the ACM|volume=34|issue=3|pages=596–615|doi=10.1145/28869.28874|s2cid=7904683|issn=0004-5411|doi-access=free}}</ref>
*1983: Data structures and network algorithms, RE Tarjan, Society for industrial and Applied Mathematics<ref>{{Cite journal|date=January 1983|title=Back Matter|url=https://epubs.siam.org/doi/pdf/10.1137/1.9781611970265.bm|journal=Data Structures and Network Algorithms|pages=125–131|doi=10.1137/1.9781611970265.bm|isbn=978-0-89871-187-5}}</ref>
*1988: A new approach to the maximum-flow problem, V Goldberg, RE Tarjan, Journal of the ACM (JACM) 35 (4), 921-940<ref>{{Cite journal|last1=Goldberg|first1=Andrew V.|last2=Tarjan|first2=Robert E.|date=1988-10-01|title=A new approach to the maximum-flow problem|journal=Journal of the ACM|volume=35|issue=4|pages=921–940|doi=10.1145/48014.61051|s2cid=14492800|issn=0004-5411|doi-access=free}}</ref>

==Patents==

Tarjan holds at least 18 U.S. patents.<ref name="CV">{{cite web|url=https://www.cs.princeton.edu/~ret/Vita-Tarjan2019.pdf|title=Curriculum Vitae|first=Robert Endre|last=Tarjan|date=November 15, 2019|archive-url=https://web.archive.org/web/20191123024149/https://www.cs.princeton.edu/~ret/Vita-Tarjan2019.pdf|archive-date=2019-11-23|access-date=2019-11-23}}</ref> These include:

* J. Bentley, D. Sleator, and R. E. Tarjan, U. S. Patent 4,796,003, ''Data Compaction'', 1989<ref>{{cite web|url=http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=4,796,003.PN.&OS=PN/4,796,003&RS=PN/4,796,003|title=United States Patent 4796003 — Data compaction|last1=Bentley|first1=Jon L.|last2=Sleator|first2=Daniel D. K.|last3=Tarjan|first3=Robert E.|date=January 3, 1989}}</ref>
* 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<ref>{{cite web|url=http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=7,818,272.PN.&OS=PN/7,818,272&RS=PN/7,818,272|title=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|first1=Mishra|last1=Nina|last2=Schreiber|first2=Robert Samuel|first3=Tarjan|last3=Robert E.|date=October 19, 2010}}</ref>
* B. Pinkas, S. Haber, R. E. Tarjan, and T. Sander, U. S. Patent 8220036, ''Establishing a secure channel with a human user'', 2012<ref>{{cite web|url=http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8220036.PN.&OS=PN/8220036&RS=PN/8220036|title=United States Patent 8220036 — Establishing a secure channel with a human user|last1=Pinkas|first1=Binyamin|last2=Haber|first2=Stuart A.|last3=Tarjan|first3=Robert E.|last4=Sander|first4=Tomas|date=July 10, 2012}}</ref>

==Notes==
{{Reflist}}

==References==
* {{cite book
 | last = Tarjan
 | first = Robert E.
 | title = Data structures and network algorithms
 | publisher = Society for Industrial and Applied Mathematics
 | location = Philadelphia
 | year = 1983
 | isbn = 978-0-89871-187-5
 | oclc = 10120539
}}
* {{cite book
 | last = Tarjan
 | first = Robert E. |author2=Pólya, George |author3=Woods, Donald R.
 | title = Notes on introductory combinatorics
 | url = https://archive.org/details/notesonintroduct00geor
 | url-access = registration
 | publisher = Birkhauser
 | location = Boston
 | year = 1983
 | isbn = 978-0-8176-3170-3
 | oclc =  10018128
}}
* [http://worldcat.org/search?q=au%3ARobert+E+Tarjan OCLC entries] for Robert E Tarjan
* {{DBLP |name=Robert E. Tarjan}}

==External links==
{{commons}}
*{{DBLP |name=Robert E. Tarjan}}
*[http://www.ipexl.com/directory/en/inventor/Tarjan_Robert_E_1.html List of Robert Tarjan's patents on IPEXL's Patent Directory]
*[http://www.cs.princeton.edu/~ret/ Robert Tarjan's home page at Princeton].
*{{MathGenealogy |name=Robert Endre Tarjan}}

{{Kanellakis Award laureates}}
{{Nevanlinna Prize winners}}
{{Turing award}}
{{Authority control}}

{{DEFAULTSORT:Tarjan, Robert}}
[[Category:1948 births]]
[[Category:Living people]]
[[Category:Members of the United States National Academy of Sciences]]
[[Category:American theoretical computer scientists]]
[[Category:Turing Award laureates]]
[[Category:Nevanlinna Prize laureates]]
[[Category:Scientists at Bell Labs]]
[[Category:California Institute of Technology alumni]]
[[Category:Stanford University School of Engineering alumni]]
[[Category:Princeton University faculty]]
[[Category:People from Pomona, California]]
[[Category:20th-century American Jews]]
[[Category:21st-century American Jews]]
[[Category:Fellows of the Society for Industrial and Applied Mathematics]]
[[Category:Summer Science Program]]
[[Category:Members of the United States National Academy of Engineering]]
[[Category:Graph theorists]]
[[Category:Members of the American Philosophical Society]]
[[Category:1994 fellows of the Association for Computing Machinery]]
[[Category:American people of Hungarian-Jewish descent]]