**An Improved Bidirectional Heuristic Search Algorithm**

Lenie Sint, Dennis de Champeaux

Pages: 177-191

DOI: 10.1145/322003.322004

A modification of Pohl's bidirectional heuristic search algorithm is described together with a simplified implementation. Theorems are proved about conditions yielding shortest paths. The results are given of a worst-case analysis of different...

**Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization**

F. T. Boesch, J. F. Gimpel

Pages: 192-198

DOI: 10.1145/322003.322005

A point-disjoint path cover of a directed graph is a collection of point-disjoint paths (some paths possibly having zero length) which covers all the points. A path cover which minimizes the number of paths corresponds to an optimal sequence of...

**Hashing Schemes for Extendible Arrays**

Arnold L. Rosenberg, Larry J. Stockmeyer

Pages: 199-221

DOI: 10.1145/322003.322006

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely hashing schemes that...

**A Queueing Model of Multiprogrammed Computer Systems Under Full Load Conditions**

Alexandre Brandwajn

Pages: 222-240

DOI: 10.1145/322003.322007

This paper presents a queueing model of a multiprogrammed computer system with virtual memory. Two system organizations are considered: (i) all the processes present in the system share primary storage; (ii) processes which have generated a file...

**On Certain Output-Buffer Management Techniques—A Stochastic Model**

Micha Hofri

Pages: 241-249

DOI: 10.1145/322003.322008

A queueing-type model is used to analyze the storage requirements of a component of a real-time data entry system. The objectives and criteria of the buffer management procedure are identified and related to the variables of the model. Both...

**Product Form and Local Balance in Queueing Networks**

K. Mani Chandy, John H. Howard, Jr., Donald F. Towsley

Pages: 250-263

DOI: 10.1145/322003.322009

A new property of queueing discipline, station balance, seems to explain why some disciplines yield product form solutions for queues and networks using nonexponential service disciplines and other disciplines do not. A queueing...

**The Power of Dominance Relations in Branch-and-Bound Algorithms**

Toshihide Ibaraki

Pages: 264-279

DOI: 10.1145/322003.322010

A dominance relation D is a binary relation defined on the set of partial problems generated in a branch-and-bound algorithm, such that PiDPj (where...

**Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors**

Oscar H. Ibarra, Chul E. Kim

Pages: 280-289

DOI: 10.1145/322003.322011

The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log...

**Information Content of Programs and Operation Encoding**

Eric C. R. Hehner

Pages: 290-297

DOI: 10.1145/322003.322012

The problem of determining the minimum representation of programs for execution by a computer is considered. The methods of measuring space requirements suggest practical methods for encoding programs and for designing machine languages. An...

**Proof, Completeness, Transcendentals, and Sampling**

Philip J. Davis

Pages: 298-310

DOI: 10.1145/322003.322013

This paper considers informally the relationship between computer aided mathematical proof, formal algebraic languages, computation with transcendental numbers, and proof by sampling.

**Algebras Having Linear Multiplicative Complexities**

C. M. Fiduccia, Y. Zalcstein

Pages: 311-331

DOI: 10.1145/322003.322014

The foundations are laid for a theory of multiplicative complexity of algebras and it is shown how “multiplication problems” such as multiplication of matrices, polynomials, quaternions, etc., are instances of this theory. The...

**On Time Versus Space**

John Hopcroft, Wolfgang Paul, Leslie Valiant

Pages: 332-337

DOI: 10.1145/322003.322015

It is shown that every deterministic multitape Turing machine of time complexity t(n) can be simulated by a deterministic Turing machine of tape complexity...

**Even Simple Programs Are Hard To Analyze**

Neil D. Jones, Steven S. Muchnick

Pages: 338-350

DOI: 10.1145/322003.322016

A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are...