Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 36 Issue 2, April 1989

Rasterizing curves of constant width
John D. Hobby
Pages: 209-229
DOI: 10.1145/62044.62045
This paper gives a fast, linear-time algorithm for generating high-quality pixel representations of curved lines. The results are similar to what is achieved by selecting a circle whose diameter is the desired line width, and turning on all...

A model for concurrency in nested transactions systems
Catriel Beeri, Philip A. Bernstein, Nathan Goodman
Pages: 230-269
DOI: 10.1145/62044.62046
Today's standard model for database concurrency control, called serializability theory, represents executions of transactions as partial orders of operations. The theory tells when an execution is serializable, that is, when the set of...

Average case selection
Walter Cunto, J. Ian Munro
Pages: 270-279
DOI: 10.1145/62044.62047
It is shown that n + k - O(1) comparisons are necessary, on average, to find the kth smallest of n numbers (kn/2). This...

On the path length of binary trees
Rolf Klein, Derick Wood
Pages: 280-289
DOI: 10.1145/62044.62048
It is shown that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound ExternalPathLength≤N...

Optimum combinations of sorting and merging
G. K. Manacher, T. D. Bui, T. Mai
Pages: 290-334
DOI: 10.1145/62044.62049
In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t. These values form a partial cover of constant density not...

Efficient dispersal of information for security, load balancing, and fault tolerance
Michael O. Rabin
Pages: 335-348
DOI: 10.1145/62044.62050
An Information Dispersal Algorithm (IDA) is developed that breaks a file F of length L = ↿ F↾ into n pieces Fi, l ≤...

A generalized algorithm for centrality problems on trees
Arnon Rosenthal, José A. Pino
Pages: 349-361
DOI: 10.1145/62044.62051
A general framework is presented for rapidly analyzing tree networks to compute a measure of the centrality or eccentricity of all vertices in the tree. Several problems, which have been previously described in...

Size-time complexity of Boolean networks for prefix computations
G. Bilardi, F. P. Preparata
Pages: 362-382
DOI: 10.1145/62044.62052
The prefix problem consists of computing all the products x0x1xj (j = 0, … , N -...

Probabilistic inductive inference
L. Pitt
Pages: 383-433
DOI: 10.1145/62044.62053
Inductive inference machines construct programs for total recursive functions given only example values of the functions. Probabilistic inductive inference machines are defined, and for various criteria of successful inference,...