Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 37 Issue 2, April 1990

Cost-error relationships in A* tree-searching
Henry W. Davis
Pages: 195-199
DOI: 10.1145/77600.77595
Pearl has shown that, in admissible A* tree-searching, the expected number of nodes expanded is bounded above and below by exponential functions of heuristic error. An additional assumption required for the validity of Pearl's argument is...

Lower bounds for orthogonal range searching: I. The reporting case
Bernard Chazelle
Pages: 200-212
DOI: 10.1145/77600.77614
We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of n points in d-space and a box [a1,...

Faster algorithms for the shortest path problem
Ravindra K. Ahuja, Kurt Mehlhorn, James Orlin, Robert E. Tarjan
Pages: 213-223
DOI: 10.1145/77600.77615
Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n vertices,...

The cost distribution of clustering in random probing
Béla Bollobás, Andrei Z. Broder, Istvan Simon
Pages: 224-237
DOI: 10.1145/77600.77619
A new approach to the analysis of random probing hashing algorithms is presented. The probability-generating function in closed form for the asymptotic cost of insertion via random probing with secondary clustering is derived. For higher-order...

A trade-off between information and communication in broadcast protocols
Baruch Awerbuch, Oded Goldreich, Ronen Vainish, David Peleg
Pages: 238-256
DOI: 10.1145/77600.77618
This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all processors...

Concurrency and availability as dual properties of replicated atomic data
M. Herlihy
Pages: 257-278
DOI: 10.1145/77600.77616
A replicated data object is a typed object that is stored redundantly at multiple locations in a distributed system. Each of the object's operations has a set of quorums, which are sets of sites whose cooperation is needed to execute that...

Nonclausal deduction in first-order temporal logic
Martín Abadi, Zohar Manna
Pages: 279-317
DOI: 10.1145/77600.77617
This paper presents a proof system for first-order temporal logic. The system extends the nonclausal resolution method for ordinary first-order logic with equality, to handle quantifiers and temporal operators. Soundness and completeness issues...

The maximum concurrent flow problem
Farhad Shahrokhi, D. W. Matula
Pages: 318-334
DOI: 10.1145/77600.77620
The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of entities can send and receive flow concurrently. The ratio of the flow supplied between a pair of entities to the predefined demand for that pair...

Module algebra
J. A. Bergstra, J. Heering, P. Klint
Pages: 335-372
DOI: 10.1145/77600.77621
An axiomatic algebraic calculus of modules is given that is based on the operators combination/union, export, renaming, and taking the visible signature. Four different models of module algebra are discussed and...

On the execution of parallel programs on multiprocessor systems—a queuing theory approach
François Baccelli, Zhen Liu
Pages: 373-414
DOI: 10.1145/77600.77622
The new class of queuing models, called Synchronized Queuing Networks, is proposed for evaluating the performance of multiprogrammed and multitasked multiprocessor systems, where workloads consists of parallel programs of...

Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Ker-I Ko
Pages: 415-438
DOI: 10.1145/77600.77623
The probabilistic polynomial-time hierarchy (BPH) is the hierarchy generated by applying the BP-operator to the Meyer-Stockmeyer polynomial-time hierarchy (PH), where the BP-operator is the natural generalization of the probabilistic complexity...