D-Index & Metrics Best Publications

D-Index & Metrics

Discipline name D-index D-index (Discipline H-index) only includes papers and citation values for an examined discipline in contrast to General H-index which accounts for publications across all disciplines. Citations Publications World Ranking National Ranking
Computer Science D-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.

Best 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

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

Contact us

Best 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

Prosenjit Bose

Prosenjit Bose

Carleton University

Publications: 69

Trending Scientists

Jay R. Ritter

Jay R. Ritter

University of Florida

Brian Donald Hart

Brian Donald Hart

Cisco Systems (China)

Jeremias H. R. Kägi

Jeremias H. R. Kägi

University of Zurich

Qian Zhang

Qian Zhang

Chinese Academy of Sciences

Xiaogang Peng

Xiaogang Peng

Zhejiang University

Harm H. Kampinga

Harm H. Kampinga

University Medical Center Groningen

Levon M. Khachigian

Levon M. Khachigian

UNSW Sydney

Mário Sousa

Mário Sousa

University of Porto

Lawrence E. Samelson

Lawrence E. Samelson

National Institutes of Health

Thomas J. Owens

Thomas J. Owens

University of South Carolina

Christian Griebler

Christian Griebler

University of Vienna

Manlio Ferrarini

Manlio Ferrarini

University of Genoa

Reinhard Pekrun

Reinhard Pekrun

Australian Catholic University

Charmine E. J. Härtel

Charmine E. J. Härtel

University of Queensland

Suzanne Craft

Suzanne Craft

Wake Forest University

Ema Ushioda

Ema Ushioda

University of Warwick

Something went wrong. Please try again later.