**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...