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