ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 32 Issue 3, July 1985

Generalized best-first search strategies and the optimality of A*
Rina Dechter, Judea Pearl
Pages: 505-536
DOI: 10.1145/3828.3830
This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated...

Enumeration of structured flowcharts
Edward A. Bender, Jon T. Butler
Pages: 537-548
DOI: 10.1145/3828.3832
An analysis of structured flowcharts is presented, where size is measured by the number, n, of decision nodes (IF-THEN-ELSE and DO-WHILE nodes). For all classes of structured flowcharts considered, the number of charts is...

Optimal attack and reinforcement of a network
William H. Cunningham
Pages: 549-561
DOI: 10.1145/3828.3829
In a nonnegative edge-weighted network, the weight of an edge represents the effort required by an attacker to destroy the edge, and the attacker derives a benefit for each new component created by destroying edges. The attacker may want to...

A simple on-line bin-packing algorithm
C. C. Lee, D. T. Lee
Pages: 562-572
DOI: 10.1145/3828.3833
The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONICM, is presented. It is shown that...

A model of computation for VLSI with related complexity results
Bernard Chazelle, Louis Monier
Pages: 573-588
DOI: 10.1145/3828.3834
A new model of computation for VLSI, based on the assumption that time for propagating information is at least linear in the distance, is proposed. While accommodating for basic laws of physics, the model is designed to be general and technology...

A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
Albert G. Greenberg, Schmuel Winograd
Pages: 589-596
DOI: 10.1145/3828.214125
A problem related to the decentralized control of a multiple access channel is considered: Suppose k stations from an ensemble of n simultaneously transmit to a multiple access channel that provides the feedback...

Adding range restriction capability to dynamic data structures
Dan E. Willard, George S. Lueker
Pages: 597-617
DOI: 10.1145/3828.3839
A database is said to allow range restrictions if one may request that only records with some specified field in a specified range be considered when answering a given query. A transformation is presented that enables range restrictions to be...

A mean value performance model for locking in databases: the no-waiting case
Y. C. Tay, Rajan Suri, Nathan Goodman
Pages: 618-651
DOI: 10.1145/3828.3831
A new performance model for dynamic locking is proposed. It is based on a flow diagram and uses only the steady state average values of the variables. It is general enough to handle nonuniform access, shared locks, static locking, multiple...

Self-adjusting binary search trees
Daniel Dominic Sleator, Robert Endre Tarjan
Pages: 652-686
DOI: 10.1145/3828.3835
The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an...

Uniform hashing is optimal
Andrew C. Yao
Pages: 687-693
DOI: 10.1145/3828.3836
It was conjectured by J. Ullman that uniform hashing is optimal in its expected retrieval cost among all open-address hashing schemes [4]. In this paper, we show that, for any open-address hashing scheme, the expected cost of retrieving a record...

Generating binary trees using rotations
David Zerling
Pages: 694-701
DOI: 10.1145/3828.214141
A new algorithm that, for the first time, exploits the rotational geometry of binary trees is developed in order to allow for the lexicographic generation of computer representations of these trees in average time O(1) per tree....

Iterative aggregation/disaggregation techniques for nearly uncoupled markov chains
Wei-Lu Cao, William J. Stewart
Pages: 702-719
DOI: 10.1145/3828.214137
Iterative aggregation/disaggregation methods provide an efficient approach for computing the stationary probability vector of nearly uncoupled (also known as nearly completely decomposable) Markov chains. Three such methods that have appeared in...

The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
Udi Manber, Martin Tompa
Pages: 720-732
DOI: 10.1145/3828.3838
This work generalizes decision trees in order to study lower bounds on the running times of algorithms that allow probabilistic, nondeterministic, or alternating control. It is shown that decision trees that are allowed internal randomization...

The complexity of propositional linear temporal logics
A. P. Sistla, E. M. Clarke
Pages: 733-749
DOI: 10.1145/3828.3837
The complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics. It is shown that these problems are NP-complete for the logic with F and are...