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. |