A Self-Stabilizing K-clustering algorithm using an arbitrary metric (2008)
Caron, E., Datta, A.K., Depardon, B., Larmore, L.L.
24 pages, figures, 11 références bibliographiques
Synchronization Algorithms on Oriented Chains (2008)
D. Bein, A.K. Datta, L.L. Larmore
We present a space- and time-optimal self-stabilizing algorithm, SSDS, for a given synchronization problem on asynchronous oriented chains. SSDS is uniform and works under the unfair distributed...
Construction of Optimal Binary Split Trees in the Presence of Bounded Access Probabilities (2007)
Hester Hirschberg, J. H. Hester, D. S. Hirschberg, L. L. Larmore
A binary split tree is a search structure combining features of heaps and binary search trees. The fastest known algorithm for building an optimal binary split tree requires \Theta(n 4 ) time if the...
D. S. Hirschberg, L.L. Larmore
The Traveler's Problem (TP) entails determining the maximum distance that can be traversed along a road, given the locations and room rates of inns along that road, and given the constraints of...
Constructing Trees in Parallel (1989)
M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. L. Miller, S-H. Teng
O(log = log n processor as well as O(log n) = log n processor CREW deterministic parallel algorithms are presented for constructing Huffman codes from a given list of frequencies. The time can be...
New Applications of Failure Functions (1987)
D. S. Hirschberg, L. L. Larmore
Several algorithms are presented whose operations are governed by a principle of failure functions: when searching for an extremal value within a sequence, it suffices to consider only the...
Subtree Weight Ratios for Optimal Binary Search Trees (1986)
Hirschberg Larmore, D. S. Hirschberg, L. L. Larmore, M. Molodowitch
For an optimal binary search tree T with a subtree S(d) at a distance d from the root of T, we study the ratio of the weight of S(d) to the weight of T. The maximum possible value, which we call...
Average Case Analysis of Marking Algorithms (1986)
D. S. Hirschberg, L.L. Larmore
. The Lindstrom marking algorithm uses bounded workspace. Its time complexity is O(n 2 ) in all cases, but it has been assumed that the average case time complexity is O(n lg n). It is proven that...
Efficient Optimal Pagination of Scrolls (1985)
Larmore California, L. L. Larmore, D. S. Hirschberg
Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O#(n lg n) time and O#(n) space, solving a problem posed by...