Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 24 Issue 2, April 1977

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