Informatiker, geb. 30.4. 1948 Pomona (Calif.).

Tarjan schloß 1969 die erste Phase seines Studiums am California Institute of Technology in Pasadena (Calif.) ab und setzte es an der Universität in Stanford fort, an der er 1972 promovierte, und nach einer Assistenzprofessur an der Cornell Universität in Ithaca (NY) ab 1974 als Assistant bzw. ab 1977 als Associate Professor lehrte. 1980 nahm er eine Tätigkeit bei den Bell Labs von AT& T auf, die er bis 1990 ausübte. Gleichzeitig war er ab 1985 Professor an der Universität in Princeton (NJ.).

Tarjans Forschungen konzentrieren sich auf die Entwicklung effektiver Algorithmen, um Rechnungen auf Computern auszuführen. Er zog dazu vorrangig kombinatorische, insbesondere graphentheoretischen Methoden heran und schuf Algorithmen von großer Eleganz. Er entwickelte Testverfahren, um einen Graphen als planar nachzuweisen, und konstruierte für den Fall, daß eine planare Einbettung des Graphen existiert, diese Einbettung, wobei die Rechenzeit nur linear proportional der Anzahl der Kanten des Graphen ist. Seine Analyse der Schleifenstruktur gewisser gerichteter Graphen lieferte wichtige Resultate für die globale Strukturanalyse von Computerprogrammen.

Durch Tarjans Untersuchungen wurden zahlreiche bekannte Algorithmen verbessert und hoch effiziente neue geschaffen, die u. a. neue Lösungsverfahren für Probleme der numerischen Analysis ermöglichten. Neben der Graphentheorie hat Tarjan mit seinen Arbeiten die Komplexitätstheorie, die Computergeometrie und die Theorie der Datenstrukturen wesentlich bereichert.

1982 wurde Tarjan für seine Leistungen mit dem Nevanlinna-Preis geehrt.