H-Index & Metrics Top Publications

H-Index & Metrics

Discipline name H-index Citations Publications World Ranking National Ranking
Computer Science H-index 111 Citations 83,477 317 World Ranking 80 National Ranking 49

Research.com Recognitions

Awards & Achievements

2009 - SIAM Fellow For the design and analysis of algorithms.

2003 - Member of the European Academy of Sciences

1999 - ACM Paris Kanellakis Theory and Practice Award Splay Tree Data Structure

1994 - ACM Fellow For fundamental achievements in the design and analysis of algorithms and data structures.

1990 - Fellow of the American Association for the Advancement of Science (AAAS)

1990 - Fellow of the American Association for the Advancement of Science (AAAS)

1988 - Member of the National Academy of Engineering For fundamental achievements in the design and analysis of data structures and computer algorithms.

1987 - Member of the National Academy of Sciences

1986 - A. M. Turing Award For fundamental achievements in the design and analysis of algorithms and data structures.

1985 - Fellow of the American Academy of Arts and Sciences

1982 - Rolf Nevanlinna Prize "Received the first Nevanlinna Prize for outstanding contributions to mathematical aspects of information science. "Pure mathematics enjoys the luxury of studying its constructions, whether finite or infinite, in complete independence of all questions of efficiency." explained Jacob Schwartz, who spoke on Tarjan's work. "By contrast, theoretical computer science must ultimately concern itself with computing engines which operate with limited speed and data storage, and therefore must take efficiency as one of its central concerns. Two closely related activities, algorithm design and algorithm analysis, grow out of this inevitable concern."[8]

1978 - Fellow of John Simon Guggenheim Memorial Foundation

Overview

What is he best known for?

The fields of study he is best known for:

  • Algorithm
  • Combinatorics
  • Programming language

Robert E. Tarjan mainly focuses on Combinatorics, Algorithm, Discrete mathematics, Spanning tree and Time complexity. His works in Directed graph, Line graph, Binary logarithm, Planar graph and Graph theory are all subjects of inquiry into Combinatorics. The various areas that Robert E. Tarjan examines in his Algorithm study include Theoretical computer science, Shortest path problem, Integer, Disjoint sets and Floyd–Warshall algorithm.

His Spanning tree study combines topics in areas such as Fibonacci heap, Graph, Data structure and Minimum spanning tree. In his research, Amortized analysis is intimately related to Min-max heap, which falls under the overarching field of Fibonacci heap. His work carried out in the field of Time complexity brings together such families of science as Linear space and Chordal graph.

His most cited work include:

  • Depth-First Search and Linear Graph Algorithms (4695 citations)
  • Fibonacci heaps and their uses in improved network optimization algorithms (2209 citations)
  • Amortized efficiency of list update and paging rules (1828 citations)

What are the main themes of his work throughout his whole career to date?

Robert E. Tarjan spends much of his time researching Combinatorics, Discrete mathematics, Algorithm, Data structure and Time complexity. Much of his study explores Combinatorics relationship to Amortized analysis. Robert E. Tarjan combines subjects such as Heap and Fibonacci heap with his study of Discrete mathematics.

His Algorithm study integrates concerns from other disciplines, such as Graph, Theoretical computer science, Maximum flow problem, Shortest path problem and Simple. His Theoretical computer science study combines topics from a wide range of disciplines, such as Weight-balanced tree and Ternary search tree. Robert E. Tarjan usually deals with Maximum flow problem and limits it to topics linked to Push–relabel maximum flow algorithm and Flow network.

He most often published in these fields:

  • Combinatorics (55.79%)
  • Discrete mathematics (38.77%)
  • Algorithm (36.17%)

What were the highlights of his more recent work (between 2011-2021)?

  • Combinatorics (55.79%)
  • Discrete mathematics (38.77%)
  • Algorithm (36.17%)

In recent papers he was focusing on the following fields of study:

Robert E. Tarjan mostly deals with Combinatorics, Discrete mathematics, Algorithm, Disjoint sets and Data structure. His Combinatorics research is multidisciplinary, incorporating perspectives in AVL tree, Amortized analysis and Set. His Discrete mathematics research incorporates elements of Fibonacci heap, Pairing heap, Skew heap, d-ary heap and Control flow graph.

His biological study spans a wide range of topics, including Maximum flow problem and Connected component. In his study, Concurrent algorithm, Sequential algorithm and Parallel random-access machine is strongly linked to Ackermann function, which falls under the umbrella field of Disjoint sets. His studies in Data structure integrate themes in fields like Class, Upper and lower bounds and Pointer.

Between 2011 and 2021, his most popular works were:

  • Software self-checking systems and methods (151 citations)
  • Finding Minimum-cost Flows by Double Scaling (108 citations)
  • Improved Time Bounds for the Maximum Flow Problem (97 citations)

In his most recent research, the most cited papers focused on:

  • Algorithm
  • Programming language
  • Operating system

His main research concerns Discrete mathematics, Algorithm, Combinatorics, Disjoint sets and Maximum flow problem. His Discrete mathematics research incorporates themes from Scapegoat tree, Binomial heap, Skew heap, d-ary heap and AVL tree. Robert E. Tarjan has researched Algorithm in several fields, including Flow and Numerical analysis.

His Combinatorics research is multidisciplinary, incorporating elements of Amortized analysis and Data analysis. His Disjoint sets research includes themes of Span tree, Construct, Rank and Independent spanning trees. His Maximum flow problem research is multidisciplinary, relying on both Segmentation, Object, Adjacency list, Series and Integer.

This overview was generated by a machine learning system which analysed the scientist’s body of work. If you have any feedback, you can contact us here.

Top Publications

Depth-First Search and Linear Graph Algorithms

Robert Endre Tarjan.
SIAM Journal on Computing (1972)

7598 Citations

Fibonacci heaps and their uses in improved network optimization algorithms

Michael L. Fredman;Robert Endre Tarjan.
Journal of the ACM (1987)

3664 Citations

Data Structures and Network Algorithms

Robert Endre Tarjan.
(1983)

3041 Citations

A new approach to the maximum-flow problem

Andrew V. Goldberg;Robert E. Tarjan.
Journal of the ACM (1988)

2928 Citations

Amortized efficiency of list update and paging rules

Daniel D. Sleator;Robert E. Tarjan.
Communications of The ACM (1985)

2729 Citations

Efficiency of a Good But Not Linear Set Union Algorithm

Robert Endre Tarjan.
Journal of the ACM (1975)

1707 Citations

A Separator Theorem for Planar Graphs

Richard J. Lipton;Robert Endre Tarjan.
Siam Journal on Applied Mathematics (1979)

1648 Citations

Self-adjusting binary search trees

Daniel Dominic Sleator;Robert Endre Tarjan.
Journal of the ACM (1985)

1595 Citations

Time bounds for selection

Manuel Blum;Robert W. Floyd;Vaughan Pratt;Ronald L. Rivest.
Journal of Computer and System Sciences (1973)

1564 Citations

Efficient Planarity Testing

John Hopcroft;Robert Tarjan.
Journal of the ACM (1974)

1553 Citations

Profile was last updated on December 6th, 2021.
Research.com Ranking is based on data retrieved from the Microsoft Academic Graph (MAG).
The ranking h-index is inferred from publications deemed to belong to the considered discipline.

If you think any of the details on this page are incorrect, let us know.

Contact us

Top Scientists Citing Robert E. Tarjan

David Eppstein

David Eppstein

University of California, Irvine

Publications: 158

Michael T. Goodrich

Michael T. Goodrich

University of California, Irvine

Publications: 101

Giuseppe F. Italiano

Giuseppe F. Italiano

Guido Carli Free International University for Social Studies

Publications: 99

Danny Z. Chen

Danny Z. Chen

University of Notre Dame

Publications: 95

Roberto Tamassia

Roberto Tamassia

Brown University

Publications: 88

Kurt Mehlhorn

Kurt Mehlhorn

Max Planck Institute for Informatics

Publications: 85

Micha Sharir

Micha Sharir

Tel Aviv University

Publications: 85

Pankaj K. Agarwal

Pankaj K. Agarwal

Duke University

Publications: 82

Gonzalo Navarro

Gonzalo Navarro

University of Chile

Publications: 79

Andrew V. Goldberg

Andrew V. Goldberg

Amazon (United States)

Publications: 77

Mikkel Thorup

Mikkel Thorup

University of Copenhagen

Publications: 77

Fedor V. Fomin

Fedor V. Fomin

University of Bergen

Publications: 74

Susanne Albers

Susanne Albers

Technical University of Munich

Publications: 73

Hans L. Bodlaender

Hans L. Bodlaender

Utrecht University

Publications: 70

Bernard Chazelle

Bernard Chazelle

Princeton University

Publications: 69

Something went wrong. Please try again later.