Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 37 Issue 3, July 1990

Lower bounds for orthogonal range searching: part II. The arithmetic model
Bernard Chazelle
Pages: 439-463
DOI: 10.1145/79147.79149
Lower bounds on the complexity of orthogonal range searching in the static case are established. Specifically, we consider the following dominance search problem: Given a collection of n weighted points in...

A fast algorithm for optimal length-limited Huffman codes
Lawrence L. Larmore, Daniel S. Hirschberg
Pages: 464-473
DOI: 10.1145/79147.79150
An O(nL)-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n, where each code string must have length no greater than L. The...

On the equivalence of an Egd to a set of Fd's
Marc H. Graham, Ke Wang
Pages: 474-490
DOI: 10.1145/79147.79151
The question “Is a given join dependency equivalent to some set of multivalued dependencies?” led to the development of acyclicity theory [1]. The central question of this paper is: “Is a given equality-generating dependency...

Analysis of database performance with dynamic locking
In Kyung Ryu, Alexander Thomasian
Pages: 491-523
DOI: 10.1145/79147.79152
A detailed model of a transaction processing system with dynamic locking is developed and analyzed. Transaction classes are distinguished on the basis of the number of data items accessed and the access mode (read-only/update). The performance...

Renaming in an asynchronous environment
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, Rüdiger Reischuk
Pages: 524-548
DOI: 10.1145/79147.79158
This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems,...

Knowledge and common knowledge in a distributed environment
Joseph Y. Halpern, Yoram Moses
Pages: 549-587
DOI: 10.1145/79147.79161
Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system...

Parallel asynchronous algorithms for discrete data
Aydin Üresin, Michel Dubois
Pages: 588-606
DOI: 10.1145/79147.79162
Many problems in the area of symbolic computing can be solved by iterative algorithms. Implementations of these algorithms on multiprocessors can be synchronous or asynchronous. Asynchronous implementations are potentially more efficient because...

Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
Ariel Orda, Raphael Rom
Pages: 607-625
DOI: 10.1145/79147.214078
In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting...

An efficient and fast parallel-connected component algorithm
Yujie Han, Robert A. Wagner
Pages: 626-642
DOI: 10.1145/79147.214077
A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the...

Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results
K. R. Pattipati, M. M. Kostreva, J. L. Teele
Pages: 643-673
DOI: 10.1145/79147.214074
This paper is concerned with the properties of nonlinear equations associated with the Scheweitzer-Bard (S-B) approximate mean value analysis (MVA) heuristic for closed product-form queuing networks. Three forms of nonlinear S-B approximate MVA...

Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
Yuri Gurevich
Pages: 674-687
DOI: 10.1145/79147.214070
A technique is developed for establishing lower bounds on the computational complexity of certain natural problems. The results have the form of time-space trade-off and exhibit the power of nondeterminism. In particular, a form of the clique...