Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 6, Nov. 2000

Minimizing stall time in single and parallel disk systems
Susanne Albers, Naveen Garg, Stefano Leonardi
Pages: 969-986
DOI: 10.1145/355541.355542
We study integrated prefetching and caching problems following the work of Cao et al. [1995] and Kimbrel and Karlin [1996]. Cao et al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and...

On the sorting-complexity of suffix tree construction
Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan
Pages: 987-1011
DOI: 10.1145/355541.355547
The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. We present a recursive technique for building suffix trees that yields optimal algorithms in different computational models. Sorting is an inherent...

The soft heap: an approximate priority queue with optimal error rate
Bernard Chazelle
Pages: 1012-1027
DOI: 10.1145/355541.355554
A simple variant of a priority queue, called a soft heap, is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. Its novelty is to beat the logarithmic bound on the complexity of a...

A minimum spanning tree algorithm with inverse-Ackermann type complexity
Bernard Chazelle
Pages: 1028-1047
DOI: 10.1145/355541.355562
A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is 0(m &agr;(m, n)), where &agr; is the classical functional inverse of...

Contention resolution with constant expected delay
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
Pages: 1048-1096
DOI: 10.1145/355541.355567
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability distribution. Raghavan and Upfal have...