Robert Tarjan

Robert Tarjan 2010

Robert „Bob“ Endre Tarjan (* 30. April 1948 in Pomona, Kalifornien) ist ein amerikanischer Informatiker. 1986 wurde er zusammen mit John E. Hopcroft für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award ausgezeichnet.

Er ist Professor an der Princeton University und arbeitet für das amerikanische Unternehmen Hewlett-Packard.

Nach ihm sind verschiedene Algorithmen benannt:

• Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten
• Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes
• Algorithmus von Hopcroft und Tarjan
• Goldberg-Tarjan-Algorithmus zur Bestimmung eines maximalen s-t-Flusses

Daneben führte er auch die Datenstrukturen Fibonacci-Heap und Splay-Baum ein.

Leben

Tarjan studierte am Caltech im kalifornischen Pasadena Mathematik, und schloss das Bachelor-Studium 1969 ab. Er wechselte an die Stanford University, wo er 1971 seinen Master in Informatik und 1972 seinen Ph.D. in Informatik mit dem Nebenfach Mathematik machte. Seine Thesis An Efficient Planarity Algorithm wurde von Robert Floyd betreut, die Vorlesungen von Donald Ervin Knuth.

Anschließend war er für ein Jahr wissenschaftlicher Mitarbeiter an der Cornell University, dann für zwei Jahre Miller Research Fellow an der University of California, Berkeley, und von 1974 bis 1977 wissenschaftlicher Mitarbeiter und dann bis 1980 außerordentlicher Professor für Informatik an der Stanford University. 1981 bis 1985 war er außerplanmäßiger Professor an der New York University. Seit 1985 ist er James S. McDonnell Distinguished University Professor of Computer Science an der Princeton University. Von 1989 bis 1994 und wieder seit 2001 ist er dort auch Co-Director des National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science. 1996 war er Gastprofessor am MIT.

Parallel begann er 1980 auch eine Karriere in der Industrie, war zunächst bis 1989 Member of Technical Staff bei den AT&T Bell Laboratories, dann bis 1997 Fellow des NEC Research Institute, und danach bis 2001 Chefwissenschaftler von InterTrust Technologies. Im Jahr 2002 war er kurzzeitig Corporate Fellow von Compaq, und wurde bei dessen Übernahme durch Hewlett-Packard dort Chefwissenschaftler, ab 2003 dann Senior Fellow.

Unter Tarjans 25 Doktoranden sind auch die Deutschen Thomas Lengauer und Monika Henzinger.

Auszeichnungen (Auswahl)

• 1978–1979: Guggenheim-Stipendium
• 1983: Nevanlinna-Preis
• 1985: Fellow der American Academy of Arts and Sciences
• 1986: Turing Award
• 1987: Member der National Academy of Sciences
• 1988: Member der National Academy of Engineering
• 1990: Fellow der American Association for the Advancement of Science und Member der American Philosophical Society
• 1994: Fellow der ACM und der New York Academy of Sciences
• 1999: Paris Kanellakis Award
• 2004: Blaise-Pascal-Medaille
• 2009: Fellow der Society for Industrial and Applied Mathematics

Werke

• R. E. Tarjan: Data Structures and Network Algorithms. CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983. ISBN 0898711878
• G. Polya, R. E. Tarjan, D. R. Woods: Notes on Introductory Combinatorics. Birkhäuser, Boston, MA, 1983

Weblinks

• Literatur von und über Robert Tarjan im Katalog der Deutschen Nationalbibliothek und auf anderen Websites (Datensatz zu Robert Tarjan • PICA-Datensatz • Apper-Personensuche)
• Website an der Princeton University (englisch)