Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 21 Issue 3, July 1974

An Efficient Algorithm for Finding an Irredundant Set Cover
Charles R. Kime, Ramachendra P. Batni, Jeffrey D. Russell
Pages: 351-355
DOI: 10.1145/321832.321833
The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an m × n cover table, the execution time of the procedure is, in the worst case,...

The Diclique Representation and Decomposition of Binary Relations
Robert M. Haralick
Pages: 356-366
DOI: 10.1145/321832.321834
The binary relation is often a useful mathematical structure for representing simple relationships whose essence is a directed connection. To better aid in interpreting or storing a binary relation we suggest a diclique decomposition. A diclique...

Characterizations of Reducible Flow Graphs
M. S. Hecht, J. D. Ullman
Pages: 367-375
DOI: 10.1145/321832.321835
It is established that if G is a reducible flow graph, then edge (n, m) is backward (a back latch) if and only if either n = m or m dominates n in...

Efficiency of a Binary Comparison Storage Technique
E. M. Palmer, M. A. Rahimi, R. W. Robinson
Pages: 376-384
DOI: 10.1145/321832.321836
The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of...

An Algorithm for the Chromatic Number of a Graph
Chung C. Wang
Pages: 385-391
DOI: 10.1145/321832.321837
Christofides' algorithm for finding the chromatic number of a graph is improved both in speed and memory space by using a depth-first search rule to search for a shortest path in a reduced subgraph tree.

A Combinatorial Problem Related to Multimodule Memory Organizations
C. K. Wong, Don Coppersmith
Pages: 392-402
DOI: 10.1145/321832.321838
This paper deals with a combinatorial minimization problem arising from studies on multimodule memory organizations. Instead of searching for an optimum solution, a particular solution is proposed and it is demonstrated that it is close to...

Information-Theoretic Limitations of Formal Systems
Gregory J. Chaitin
Pages: 403-424
DOI: 10.1145/321832.321839
An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time...

On Almost Everywhere Complex Recursive Functions
John Gill, Manuel Blum
Pages: 425-435
DOI: 10.1145/321832.321840
Let h be a recursive function. A partial recursive function &psgr; is i.o. (infinitely often) h-complex if every program for &psgr; requires more than...

Iterated Limiting Recursion and the Program Minimization Problem
L. K. Schubert
Pages: 436-445
DOI: 10.1145/321832.321841
The general problem of finding minimal programs realizing given “program descriptions” is considered, where program descriptions may be of finite or infinite length and may specify arbitrary program properties. The problem of finding...

Context-Limited Grammars
Thomas N. Hibbard
Pages: 446-453
DOI: 10.1145/321832.321842
A phrase structure grammar is called context-limited if there exists a partial ordering on its alphabet such that any letter on the left of any production is less than some letter on the right of the same production. It is...

Computing a Subinterval of the Image
Paul L. Richman
Pages: 454-458
DOI: 10.1145/321832.321843
The problem of computing a desired function value to within a prescribed tolerance can be formulated in the following two distinct ways: Formulation I: Given x and ∈ > 0, compute f(x) to within ∈....

Application of the Diffusion Approximation to Queueing Networks II: Nonequilibrium Distributions and Applications to Computer Modeling
Hisashi Kobayashi
Pages: 459-469
DOI: 10.1145/321832.321844
Quite often explicit information about the behavior of a queue over a fairly short period is wanted. This requires solving the nonequilibrium solution of the queue-length distribution, which is usually quite difficult mathematically. The first...

Waiting Lines and Times in a System with Polling
Alan G. Konheim, Bernd Meister
Pages: 470-490
DOI: 10.1145/321832.321845
A communication system consisting of a number of buffered input terminals connected to a computer by a single channel is analyzed. The terminals are polled in sequence and the data is removed from the terminal's buffer. When the buffer has been...

Bounds for Some Functions Concerning Dynamic Storage Allocation
J. M. Robson
Pages: 491-499
DOI: 10.1145/321832.321846
The amount of store necessary to operate a dynamic storage allocation system, subject to certain constraints, with no risk of breakdown due to storage fragmentation, is considered. Upper and lower bounds are given for this amount of store, both...

Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
Mandell Bellmore, Saman Hong
Pages: 500-504
DOI: 10.1145/321832.321847
It is shown that the multisalesmen problem can be solved by solving the standard traveling salesman problem on an expanded graph. The expanded graph has m — 1 more nodes than the original graph where m is...

An Algorithm for the Bounded Variable Integer Programming Problem
L. E. Trotter, Jr., C. M. Shetty
Pages: 505-513
DOI: 10.1145/321832.321848
An algorithm is proposed for the bounded variable pure integer programming problem which treats general integer variables directly in an implicit enumeration procedure closely related to that advanced by Balas and Geoffrion for binary...

Some New Bounds on the Condition Numbers of Optimally Scaled Matrices
T. I. Fenner, G. Loizou
Pages: 514-524
DOI: 10.1145/321832.321849
New lower bounds on the minimal condition numbers of a matrix with respect to both one-sided and two-sided scaling by diagonal matrices are obtained. These bounds improve certain results obtained by F. L. Bauer.