Minimum Spanning Trees
| Basic Algorithms |
Edmonds Karp flow
| Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems |
Fibonacci heaps - Tarjan and Fredman
| Fibonacci heaps and their uses in improved network optimization algorithms |
Two algorithms for maintaining order in a list
| The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). |
Self-adjusting binary search trees - Splay Tree
| The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. |
Randomized Data Structures for the Dynamic Closest-Pair Problem
|
Randomized data structurefor solving the dynamic closest-pair problem, for finding the closest pair of a set of n points in D-dimensional space in constant time. |
A linear-time algorithm for a special case of disjoint set union
| A linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. |
The LCA problem revisited
| A very simple algorithm for the Least Common Ancestor problem |
On–line construction of suffix trees
| An on–line algorithm is presented for constructing the suffix tree for agiven string in time linear in the length of the string. |