Robert Tarjan

Robert Endre „Bob“ Tarjan (* 30. April 1948 in Pomona, Kalifornien) ist ein US-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.

Leben[Bearbeiten | Quelltext bearbeiten]

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.

Werk[Bearbeiten | Quelltext bearbeiten]

Er ist bekannt für die Entwicklung und Analyse von Algorithmen insbesondere für Graphen und Netzwerke.

Nach ihm sind verschiedene Algorithmen benannt:

• Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten^[1]
• Algorithmen von Hopcroft und Tarjan^[2]
• Goldberg-Tarjan-Algorithmus zur Bestimmung eines maximalen s-t-Flusses^[3]
• Von ihm stammt ein nach ihm benannter Algorithmus zur Bestimmung der Lowest Common Ancestors zweier Knoten in einer Baumstruktur.^[4] 1983 verbesserten Harold N. Gabow und Tarjan den Algorithmus auf Ausführung in linearer Zeit.^[5]

Von ihm und Harold N. Gabow stammt der schnellste Algorithmus für Matching auf gewichteten Graphen.^[6] Mit Manuel Blum, Robert Floyd, Vaughan Pratt und Ron Rivest^[7] entwickelte er 1973 einen approximativen Selektionsalgorithmus (Bestimmung der k-ten kleinsten Zahl in Listen und Arrays), den median of median Algorithmus. Von ihm stammt auch eine Analyse und Schranken der Zeit-Komplexität der Algorithmen zur Union-Find-Struktur.^[8][9] Mit Andrew V. Goldberg eröffnete er 1988 einen neuen Zugang zum Problem maximaler Netzwerkflüsse.^[10]

Mit David R. Karger und Philip Klein fand er 1995 einen randomisierten, in der Zeit linearen Algorithmus zur Bestimmung minimaler Spannbäume (MST-Problem).^[11] Er basiert auf dem Algorithmus von Borůvka. Für die Analyse von Algorithmen zu MST entwickelte er eine Färbemethode (siehe Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes).

Daneben führte er auch die Datenstrukturen Fibonacci-Heap^[12] und Splay-Baum^[13] ein. Fibonacci-Heaps wandte er auf die Optimierung von Netzwerkflüssen an.

Auszeichnungen[Bearbeiten | Quelltext bearbeiten]

• 1978–1979: Guggenheim-Stipendium
• 1983: Nevanlinna-Preis (Preisvortrag auf dem ICM in Warschau: Efficient algorithms for network optimization)
• 1984: NAS Award for Initiatives in Research; Frederick-W.-Lanchester-Preis^[14]
• 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 mit Sleator für den Slay-Baum
• 2004: Blaise-Pascal-Medaille
• 2009: Fellow der Society for Industrial and Applied Mathematics

Schriften[Bearbeiten | Quelltext bearbeiten]

• Data Structures and Network Algorithms, CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983, ISBN 0-89871-187-8.
• mit G. Polya, D. R. Woods: Notes on Introductory Combinatorics. Birkhäuser, Boston, MA, 1983.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Commons: Robert Tarjan – Sammlung von Bildern, Videos und Audiodateien

• Website an der Princeton University (englisch)
• Google Scholar

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

1. ↑ Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, Band 1, 1972, S. 146–160.
2. ↑ John Hopcroft, Robert Tarjan, Efficient planarity testing, Journal of the Association for Computing Machinery, Band 21, 1974, S. 549–568
3. ↑ A. V. Goldberg, R. E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM, Band 35, 1974, S. 921–940
4. ↑ Tarjan, Applications of path compression on balanced trees, Journal of the ACM, Band 26, 1979, S. 690–715
5. ↑ Gabow, Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), 1983, S. 246–251
6. ↑ Gabow, Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM, Band 38, 1991, S. 815–853
7. ↑ M. Blum, R. W. Floyd, V. R. Pratt, R. Rivest, R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, Band 7, 1973, S. 448–461.
8. ↑ Tarjan, A class of algorithms which require nonlinear time to maintain disjoint sets, Journal of Computer and System Sciences. Band 18, Nr. 2, 1979, S. 110–127
9. ↑ R. E. Tarjan, J. van Leeuwen, "Worst-case analysis of set union algorithmsm, Journal of the ACM, Band 31, 1984, S. 245–281.
10. ↑ Goldberg, Tarjan, A new approach to the maximum-flow problem, Journal of the ACM, Band 35, 1988, S. 921–940
11. ↑ David R. Karger, Philip N. Klein, Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM, Band 42, 1995, S. 321–328
12. ↑ M. L. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, Band 34, 1987, S. 596–615
13. ↑ Daniel D. Sleator, Robert Tarjan: Self-Adjusting Binary Search Trees. In: Journal of the ACM, Band 32, Nr. 3, 1985, S. 652–686
14. ↑ Frederick W. Lanchester Prize. informs.org (Institute for Operations Research and the Management Sciences), archiviert vom Original am 2. Oktober 2015; abgerufen am 16. Februar 2016 (englisch).