Haeupler, Bernhard, Sen, Siddhartha, Tarjan, Robert E.
The heap is a basic data structure used in a wide variety of applications, including shortest path and minimum spanning tree algorithms. In this paper we explore the design space of comparison-based,...
Abstract. We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation...
Computer Algorithms. Addison-Wesley, 1974. (2008)
Milton Abramowitz, Irene A. Stegun, Book Of Mathematical Functions, G. M. Adel’son-vel’skiĭ, Leonard M. Adleman, Carl Pomerance, ...
numbers from composite numbers. Annals of Mathematics, 117:173–206, 1983. [4] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of...
Abstract Design of Data Structures for Mergeable Trees ∗ (2008)
Loukas Georgiadis, Robert E. Tarjan, Renato F. Werneck
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant allows an operation that merges two...
Clustering Social Networks (2008)
Nina Mishra, Robert Schreiber, Isabelle Stanton, Robert E. Tarjan
Abstract. Social networks are ubiquitous. The discovery of close-knit clusters in these networks is of fundamental and practical interest. Existing clustering criteria are limited in that clusters...
Planar Point Location Using Persistent Search Trees (2008)
Lan Munro, Neil Sarnak, Robert E. Tarjan
ABSTRACT: A classical problem in computational geometry is the planar point location problem. This problem calls for preprocessing a polygonal subdivision of the plane defined by n line segments so...
David R. Karger, Philip N. Klein, Robert E. Tarjan
Abstract. We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently...
Dynamic Trees in Practice ⋆ (2008)
Robert E. Tarjan, Renato F. Werneck
Abstract. Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining connectivity information in logarithmic time, they can support...
Abstract Design of Data Structures for Mergeable Trees ∗ (2008)
Loukas Georgiadis, Robert E. Tarjan, Renato F. Werneck
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant allows an operation that merges two...
Editor A Locally Adaptive Data (2008)
Ian Munro, Jon Louis Bentley, Daniel D. Sleator, Robert E. Tarjan, Victor K. Wei
ABSTRACT: A data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described....
Programming Techniques and Amortized Efficiency Of List Data Structures Editor (2008)
Ellis Horowitz Update, Paging Rules, Daniel D. Sleator, Robert E. Tarjan
ABSTRACT: In this article we study the amortized efficiency of the “move-to-front ” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith...
Amortized Efficiency of List Update and Paging Rules (2008)
Ellis Horowitz, Daniel D. Sleator, Robert E. Tarjan
ABSTRACT: In this article we study the amortized efficiency of the “move-to-front ” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith...
Incremental Topological Ordering and Strong Component Maintenance (2008)
Haeupler, Bernhard, Sen, Siddhartha, Tarjan, Robert E.
We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(m^{1/2}) amortized...
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
ÔÖ�� � �Ø � Ø��Ø ��Ø × �Ò �Ø�Ñ Ü �Ò � � ×�Ø � �Ò � �Ò×Û�Ö × ÔÓ×�
James R. Driscoll, Daniel D. K. Sleator, Robert E. Tarjan
Abstract. This paper considers the problem of represmrtirrg stacks with catenation so that any stack, old or new, is available for access or update operations. Th]s problem arises in the...
A Locally Adaptive Data Compression Scheme (2008)
Ian Munro, Jon Louis Bentley, Daniel D. Sleator, Robert E. Tarjan, Andvlctor K. We
ABSTRACT: A data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described....
Incremental Topological Ordering and Strong Component Maintenance (2008)
Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan
Abstract. We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(m 1/2)...
Planarity Algorithms via PQ-Trees (2008)
Bernhard Haeupler, Robert E. Tarjan
We give a linear-time planarity test that unifies and simplifies the algorithms of Shih and Hsu and Boyer and Myrvold; in our view, these algorithms are really one algorithm with different...
Shortest Path Feasibility Algorithms: An Experimental Evaluation (2008)
Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, Renato F. Werneck
This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study...
Lower Bounds, Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Fur Informatik, Friedhelm Meyer Auf Der Heide, ...
The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a...
F. T. Leighton, Bruce M. Maggs, C. Greg Plaxton, R. Rajaraman, Andr Ea, W. Richa, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
David R. Karger, Philip N. Klein, Robert E. Tarjan
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered...
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A; B;C) replaces sets A and B...
Harold N. Gabow, Robert E. Tarjan, Haim Kaplan, Haim Kaplan
We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n...
Meldable Heaps and Boolean Union-Find (extended abstract) (2007)
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations ndmin, insert, delete, decrease-key, and meld. In the usual de nition decrease-key and...
1 A randomized algorithm to nd minimum spanning trees We'll present today a randomized linear-time algorithm to nd minimum spanning trees,
Neal E. Young, Robert E. Tarjan, James B. Orlin
We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to...
Finding a Feasible Flow in a Strongly Connected Network (2007)
Haeupler, Bernhard, Tarjan, Robert E.
We consider the problem of finding a feasible single-commodity flow in a strongly connected network with fixed supplies and demands, provided that the sum of supplies equals the sum of demands and...
Data Structures for Mergeable Trees (2007)
Georgiadis, Loukas, Kaplan, Haim, Shafrir, Nira, Tarjan, Robert E., Werneck, Renato F.
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two paths in a single...
Thin Heaps, Thick Heaps (2006)
The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra’s shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap...
Finding Minimum-Cost Circulations by Successive Approximation. (2005)
Goldberg, Andrew V., Tarjan, Robert E.
We develop a new approach to solving minimum cost circulation problems. Our approach combines methods for solving the maximum flow problems with successive approximation techniques based on cost...
Faster Scaling Algorithms for Network Problems, (2005)
Gabow, Harold N., Tarjan, Robert E.
This paper presents algorithms for the assignment problem, the transportation problem and the minimum cost flow problem of operations research. The algorithms finds a minimum cost solution, but run...
Improved Time Bounds for the Maximum Flow Problem, (2005)
Ahuma, Ravindra K., Orlin, James B., Tarjan, Robert E.
A new approach is proposed to the maximum network flow problem. The approach yields a very simple algorithm running O(n-cubed) time on n-vertex networks. Incorporation of the dynamic tree data...
Graph clustering and minimum cut trees (2004)
Gary William Flake, Robert E. Tarjan, Kostas Tsioutsiouliklis
Abstract. In this paper, we introduce simple graph clustering methods based on minimum cuts within the graph. The clustering methods are general enough to apply to any kind of graph but are well...
Melding Priority Queues (2004)
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when n is an upper bound on the number of elements in the priority queue, can be...
Melding Priority Queues (2004)
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when there are up to n elements in the priority queue, can be converted into a...
Finding dominators in practice (2004)
Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, David I. August
Abstract. The computation of dominators in a flowgraph has applications in program optimization, circuit testing, and other areas. Lengauer and Tarjan [17] proposed two versions of a fast algorithm...
Finding dominators in practice (2004)
Loukas Georgiadis, Robert E. Tarjan, Renato F. Werneck
The computation of dominators in a flowgraph has applications in several areas, including program optimization, circuit testing, and theoretical biology. Lengauer and Tarjan [30] proposed two...
Graph Clustering and Minimum Cut Trees (2003)
Flake, Gary William, Tarjan, Robert E., Tsioutsiouliklis, Kostas
In this paper, we introduce simple graph clustering methods based on minimum cuts within the graph. The clustering methods are general enough to apply to any kind of graph but are well suited for...
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs (2002)
Buchsbaum, Adam L., Georgiadis, Loukas, Kaplan, Haim, Rogers, Anne, Tarjan, Robert E., Westbrook, Jeffery R.
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a...
Algorithmic Aspects of Vertex Elimination on Directed Graphs. (2002)
Rose,Donald J., Tarjan,Robert E.
This report considers a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse systems of linear equations. Efficient algorithms are given to: (1) calculate...
A Fast Merging Algorithm. (2002)
Brown,Mark R., Tarjan,Robert E.
An algorithm which merges sorted lists is represented as balanced binary tree. If the lists have lengths m and n (m < or = n) then the merging procedure runs in 0 (m log n/m) steps, which is the same...
A Separator Theorem for Planar Graphs. (2002)
Lipton,Richard J., Tarjan,Robert E.
Let G be any n-vertex planar graph. Prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more...
Applications of a Planar Separator Theorem. (2002)
Lipton,Richard J., Tarjan,Robert E.
Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(square root of n) vertices. This separator theorem, in combination with a...
Variations of a Pebble Game on Graphs. (2002)
Gilbert,John R., Tarjan,Robert E.
Two variations are examined of a one-person pebble game played on directed graphs, which has been studied as a model of register allocation. The black-white pebble game of Cook and Sethi is shown to...
Design and Analysis of a Data Structure for Representing Sorted Lists. (2002)
Brown,Mark R., Tarjan,Robert E.
In this paper we explore the use of 2-3 trees to represent sorted lists. We analyze the worst-case cost of sequences of insertions and deletions in 2-3 trees under each of the following three...
Two Linear-Time Algorithms for Five-Coloring a Planar Graph, (2002)
Matula,David W., Shiloach,Yossi, Tarjan,Robert E.
A sequential processing algorithm using bicolor interchange that five-colors an n vertex planar graph in O(n-squared) time was given by Matula, Marble, and Isaacson. Lipton and Miller used a batch...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being xed, is a linear function of time. The kinetic heap is a simple...
Dynamic self-checking techniques for improved tamper resistance (2001)
Bill Horne, Lesley Matheson, Robert E. Tarjan
Abstract. We describe a software self-checking mechanism designed to improve the tamper resistance of large programs. The mechanism consists of a number of testers that redundantly test for changes...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
3 We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being xed, is a linear function of time. The kinetic heap is a simple...
Robustness and Security of Digital Watermarks (2000)
Lesley R. Matheson, Stephen G. Mitchell, Talal G. Shamoon, Robert E. Tarjan, Francis Zane
Digital watermarking is a nascent but promising technology that o#ers protection of unencrypted digital content. This paper is a brief technical survey of the multimedia watermarking landscape. The...
Purely functional, real-time deques with catenation (1999)
We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of...
TIGHT ANALYSES OF TWO LOCAL LOAD BALANCING ALGORITHMS (1999)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Finding the Triconnected Components of a Graph, (1998)
Hopcroft,John E., Tarjan,Robert E.
An algorithm for decomposing a graph into triconnected components is presented. The algorithm requires 0(V + E) time and space when implemented on a random access computer, where V is the number of...
Finding Minimum-Cost Circulations by Canceling Negative Cycles. (1998)
Goldberg, Andrew V., Tarjan, Robert E.
A classical algorithm for finding a minimum cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an...
A Fast Parametric Maximum Flow Algorithm. Revision, (1998)
Gallo, Giorgio, Grigoriadis, Michael D., Tarjan, Robert E.
The classical maximum flow problem sometimes occurs in settings in which the capacities are not fixed but are functions of a single parameters, and the goal is to find the value of the parameter such...
Finding Minimum-Cost Circulations by Canceling Negative Cycles, (1998)
Goldberg, Andrew V., Tarjan, Robert E.
A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an...
Finding Minimum-Cost Circulations by Successive Approximation, (1998)
Goldberg, Andrew V., Tarjan, Robert E.
This document develops a new approach to solving minimum-cost circulation problems. This approach combines methods for solving the maximum flow problem with successive approximation techniques based...
A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest, (1998)
Gabow, Harold N., Tarjan, Robert E.
A pseudoforest is a graph each of whose connected components is a tree or a tree plus an edge; a spanning pseudoforest of a graph contains the greatest number of edges possible. This paper shows that...
Relaxed Heaps: An Alternative to Fibonacci Heaps, (1998)
Driscoll, James R., Gabow, Harold N., Shrairman, Ruth, Tarjan, Robert E.
The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap - a sequence of m decrease key and n delete min operations takes time O(m + n...
Faster Algorithms for the Shortest Path Problem, (1998)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
This document investigates efficient implementations of Dijkstra's shortest path algorithm. The authors propose a new data structure, called the redistributive heap, for use in this algorithm. On a...
Amortized Analysis of Algorithms for Set Union with Backtracking. Revision, (1998)
Westbrook, Jeffrey, Tarjan, Robert E.
Mannila and Ukkonen have studied a variant of the classical disjoint set union (equivalence) problem in which an extra operation, called deunion, can undo the most recently performed union operation...
Finding Minimum-Cost Flows by Double Scaling, (1998)
Ahuja, Ravindra K., Goldberg, Andrew V., Orlin, James B., Tarjan, Robert E.
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...
Network Flow Algorithms, (1998)
Goldberg, Andrew V., Tardos, Eva, Tarjan, Robert E.
Network flow problems are central problems in operations research, computer science, and engineering and they arise in many real world applications. Starting with early work in linear programming and...
A Tight Amortized Bound for Path Reversal, (1998)
Ginat, David, Sleator, Daniel D., Tarjan, Robert E.
Path reversal is a form of path compression used in a disjoint set union algorithm and a mutual exclusion algorithm. We derive a tight upper bound on the amortized cost of path reversal. (JHD)
Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem, (1998)
Goldberg, Andrew V., Grigoriadis, Michael D., Tarjan, Robert E.
Goldfarb and Hao have proposed a network simplex algorithm that will solve a maximum flow problem on an n-vertex, m-arc network in at most nm pivots and O(n squared m) time. In this paper we describe...
Maintaining Bridge-Connected and Biconnected Components On-Line, (1998)
Westbrook, Jeffrey, Tarjan, Robert E.
We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge...
Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem, (1998)
We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a certain bound on the number of...
Simplified Linear-Time Jordan Sorting and Polygon Clipping, (1998)
Fung, Khun Y., Nicholl, Tina M., Tarjan, Robert E., Van Wyk, Christopher J.
The Jordan sorting problem is, given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the x-axis. This problem arises in clipping a simple polygon...
Almost-Optimum Parallel Speed-Ups of Algorithms for Bipartite Matching and Related Problems, (1998)
Gabow, Harold N., Tarjan, Robert E.
This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. Given is a bipartite graph with n vertices, m edges, and integral edge costs at most N in magnitude....
Faster Scaling Algorithms for General Graph Matching Problems, (1998)
Gabow, Harold N., Tarjan, Robert E.
This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. Specifically, let n,...
A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network, (1998)
Goldberg, Andrew V., Tarjan, Robert E.
We suppose a simple parallel algorithm for finding a blocking flow in an acyclic network. On an n-vertex, m-arc network, our algorithm runs in O(n log n) time and O(nm) space using an m-processor...
Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph, (1998)
Eppstein, David, Italiano, Giuseppe F., Tamassia, Roberto, Tarjan, Robert E., Westbrook, Jeffery
We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and...
Short Encodings of Evolving Structures, (1998)
Sleator, Daniel D., Tarjan, Robert E., Thurston, William P.
A derivation in a transformational system such as a graph grammar may be redundant in the sense that the exact order of the transformations may not affect the final outcome; all that matters is that...
Unique Binary Search Tree Representations and Equality-Testing of Sets and Sequences, (1998)
Sundar, Rajamani, Tarjan, Robert E.
Given an ordered universe U, we study the problem of representing each subset of U by a unique binary search tree so that dictionary operations can be performed efficiently. We exhibit...
Simple confluently persistent catenable lists (1998)
Haim Kaplan, Chris Okasaki, Robert E. Tarjan
Abstract. We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1998)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
Simple Confluently Persistent Catenable Lists (Extended Abstract) (1998)
Haim Kaplan, Chris Okasaki, Robert E. Tarjan
We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive -- each...
Dynamic Trees as Search Trees via Euler Tours, Applied to the Network Simplex Algorithm (1997)
The dynamic tree is an abstract data type that allows the maintenance of a collection of trees subject to joining by adding edges (linking) and splitting by deleting edges (cutting), while at the...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1997)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
Purely functional representations of catenable sorted lists (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Expected Performance of Dijkstra's Shortest Path Algorithm (1996)
Andrew Goldberg Nec, Andrew V. Goldberg, Robert E. Tarjan
We show that the expected number of decrease-key operations in Dijkstra's shortest path algorithm is O(n log(1 + m=n)) for an n-vertex, m-arc graph. The bound holds for any graph structure; the...
TR-511-96 Purely Functional Representations of Catenable Sorted Lists. (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling (1996)
Richard Cole, Philip N. Klein, Robert E. Tarjan
We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2 log n off the best previous running...
Expected Performance of Dijkstra's Shortest Path Algorithm (1996)
Andrew V. Goldberg, Robert E. Tarjan
We show that the expected number of decrease-key operations in Dijkstra's shortest path algorithm is O(n log(1+m=n)) for an n-vertex, m-arc graph. The bound holds for any graph structure; the...
Purely Functional Representations of Catenable Sorted Lists. (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Buchsbaum, Adam L, Sundar, Rajamani, Tarjan, Robert E
A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively...
Buchsbaum, Adam L, Sundar, Rajamani, Tarjan, Robert E
A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively...
Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan
A deque with heap order is a linear list of elements with real-valued keys which allows insertions and deletions of elements at both ends of the list. It also allows the findmin (equivalently...
Tight Analyses Of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh Leighton, F. T. Leighton, Bruce M. Maggs, C. Greg Plaxton, R. Rajaraman, Andr Ea, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees (1995)
David R. Karger, Philip N. Klein, Robert E. Tarjan
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh Leighton, Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses Of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, C. Greg Plaxton, R. Rajaraman, Robert E. Tarjan
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses Of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, C. Greg Plaxton, R. Rajaraman, Robert E. Tarjan
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses Of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, C. Greg Plaxton, R. Rajaraman, Robert E. Tarjan
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Sets In Planar, Lesley R. Matheson, Robert E. Tarjan
Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we...
A Critical Analysis of Multigrid Methods on Massively Parallel Computers (1994)
Lesley Matheson, Robert E. Tarjan
The hierarchical nature of multigrid algorithms leaves domain parallel strategies with a deficiency of parallelism as the computation moves to coarser and coarser grids. To introduce more parallelism...
A Linear-Work Parallel Algorithm for Finding Minimum Spanning Trees (1994)
Richard Cole, Philip N. Klein, Robert E. Tarjan, Philip N, Robert E
We give the first linear-work parallel algorithm for finding a minimum spanning tree. It is a randomized algorithm, and requires O(2 log 3 n log n) expected time. It is a modification of the...
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We study the parameterized complexity of several NP-Hard graph completion problems: The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop an...
Dominating Sets in Planar Graphs (1994)
Lesley R. Matheson, Robert E. Tarjan
Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we...
Improved Algorithms For Bipartite Network Flow (1994)
Ravindra K. Ahuja, James B. Orlin, Clifford Stein, Robert E. Tarjan, Robert E
. In this paper, we study network flow algorithms for bipartite networks. A network G = (V; E) is called bipartite if its vertex set V can be partitioned into two subsets V 1 and V 2 such that all...
Dynamic Perfect Hashing: Upper and Lower Bounds (1994)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Meyer Auf Der Heide, Friedhelm, Rohnert, Hans, Tarjan, Robert E.
A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees (1993)
Philip N. Klein, Philip N. Klein, Robert E. Tarjan, Robert E. Tarjan
We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random...
An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem (1993)
Jiazhen Cai, Xiaofeng Han, Robert E. Tarjan
Based on a new version of Hopcroft and Tarjan's planarity testing algorithm, we develop an O (mlogn)-time algorithm to find a maximal planar subgraph. Key words. algorithm, complexity,...
Confluently Persistent Deques via Data-Structural Bootstrapping (1993)
Adam L. Buchsbaum, Robert E. Tarjan
We introduce data-structural bootstrapping, a technique to design data structures recursively, and use it to design confluently persistent deques. Our data structure requires O(log 3 k) worstcase...
Lazy Structure Sharing for Query Optimization (1993)
Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan
We study lazy structure sharing as a tool for optimizing equivalence testing on complex data types. We investigate a number of strategies for a restricted case of the problem and provide upper and...
A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees (1993)
Philip N. Klein, Robert E. Tarjan
We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random...
Computer Science, Daniel Barbara, Frank Pittelli, Hector Garcia-molina, Hector Garcia-molina, Daniel D. Sleator, ...
s of all technical reports published by the Department of Computer Science between 1985 and 1991 are listed below. Some of these reports are available for anonymous ftp or can be purchased from the...
Randomized Parallel Algorithms For Trapezoidal Diagrams (1992)
Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan
We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm...
Verification and Sensitivity Analysis Of Minimum Spanning Trees In Linear Time (1992)
Brandon Dixon, Monika Rauch, Robert, Robert E. Tarjan
. Koml'os has devised a way to use a linear number of binary comparisons to test whether a given spanning tree of a graph with edge costs is a minimum spanning tree. The total computational work...
Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph (1992)
David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery Westbrook, Moti Yung
We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights, and...
Finding Minimum-Cost Flows by Double Scaling (1992)
Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K. Ahuja, Andrew V. Goldberg, Andrew V. Goldberg, Andrew V. Goldberg, ...
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...
Dynamic Perfect Hashing: Upper and Lower Bounds (1991)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Meyer Auf Der Heide, Friedhelm, Rohnert, Hans, Tarjan, Robert E.
The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a...
North-Holland SIMPLIFIED LINEAR-TIME JORDAN SORTING AND POLYGON CLIPPING (1990)
Khun Yee Fung, Tina M. Nicholl, Robert E. Tarjan, Christopher J. Van Wyk, Communicated D. Gries
Given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, the Jordan sorting problem is to sort them into the order in which they occur along...
Faster Algorithms for the Shortest Path Problem (1990)
Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, Robert E. Tarjan
Abstract. Efficient implementations of Dijkstra’s shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n...
FULLY PERSISTENT LISTS WITH CATENATION (1990)
James R. Driscolll, Daniel D. K. Sleator, Robert E. Tarjan
In this paper we consider the problem of efficiently implementing a set of side-effect-free procedures for manipulating lists. These procedures are: makelist ( d).-first ( X):
Faster algorithms for the shortest path problem (1990)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Making Data Structures Persistent (1989)
James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan
This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version...
A new approach to the maximum flow problem (1988)
Andrew V. Goldberg, Robert E. Tarjan
Abstract. All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length...
Improved Time Bounds for the Maximum Flow Problem (1988)
X A Er, X Xaf X, Ravindra K. Ahuja, James B. Orlin, Robert E. Tarjan, Ravindra K. Ahuja, ...
tT~~~~~~~~ ~-.- it _.r)-1.--::- I:I
Rotation distance, triangulations, and hyperbolic geometry (1988)
Daniel D. Sleator, Robert E. Tarjan, William, P. Thurston
A rotation in a binary tree is a local restructuring of the tree that changes it into another tree. One can execute a rotation by collapsing an internal edge of the tree to a point, thereby obtaining...
Dynamic Perfect Hashing: Upper and Lower Bounds (1988)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Meyer Auf Der Heide, Friedhelm, Rohnert, Hans, Tarjan, Robert E.
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Improved time bounds for the maximum flow problem (1988)
Ahuja, Ravindra K., Orlin, James B., Tarjan, Robert E.
"December 1987, revised June 1988."
Improved time bounds for the maximum flow problem (1988)
Ahuja, Ravindra K., Orlin, James B., Tarjan, Robert E.
"December 1987, revised June 1988."
James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan
This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version...
James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan
This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version...
Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees (1986)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
Sorting Jordan sequences in linear time (1985)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
Sorting Jordan sequences in linear time (1984)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
Abstract. A Separator Theorem for Planar Graphs f * (1977)
Richard J. Lipton, Robert E. Tarjan, Richard J. Lipton, Robert Andre Tarjan
Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more...