Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 23 Issue 3, July 1976

Resolution Strategies as Decision Procedures
William H. Joyner, Jr.
Pages: 398-417
DOI: 10.1145/321958.321960
The resolution principle, an automatic inference technique, is studied as a possible decision procedure for certain classes of first-order formulas. It is shown that most previous resolution strategies do not decide satisfiability even for...

Canonical Coin Changing and Greedy Solutions
Lena Chang, James F. Korsh
Pages: 418-422
DOI: 10.1145/321958.321961
A natural, and readily computable, first guess at a solution to the coin changing problem is the canonical solution. This solution is a special case of the greedy solution which is a reasonable heuristic guess for the knapsack problem. In this...

Shifting Graphs and Their Applications
Nicholas Pippenger, Leslie G. Valiant
Pages: 423-432
DOI: 10.1145/321958.321962
Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied. Bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity...

A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
Douglas C. Schmidt, Larry E. Druffel
Pages: 433-445
DOI: 10.1145/321958.321963
A backtracking algorithm for testing a pair of digraphs for isomorphism is presented. The information contained in the distance matrix representation of a graph is used to establish an initial partition of the graph's vertices. This distance...

R-Domination in Graphs
Peter J. Slater
Pages: 446-450
DOI: 10.1145/321958.321964
The problem of finding a minimum k-basis of graph G is that of selecting as small a set B of vertices as possible such that every vertex of G is at distance k...

An Analysis of Binary Search Trees Formed from Sequences of Nondistinct Keys
William H. Burge
Pages: 451-454
DOI: 10.1145/321958.321965
The expected depth of each key in the set of binary search trees formed from all sequences composed from a multiset {p1 · 1, p2 · 2,...

Semi-Implicit Runge-Kutta Procedures with Error Estimates for the Numerical Integration of Stiff Systems of Ordinary Differential Equations
J. R. Cash
Pages: 455-460
DOI: 10.1145/321958.321966
A -stable, semi-implicit Runge-Kutta procedures requiring at most one Jacobian evaluation per time step are developed for the approximate numerical integration of stiff systems of ordinary differential equations. A simple...

Scheduling Tasks with Nonuniform Deadlines on Two Processors
M. R. Garey, D. S. Johnson
Pages: 461-467
DOI: 10.1145/321958.321967
Given a set @@@@ = {T1,T2,···,Tn} of tasks, with each Ti having...

Solution of Integer Programs with a Quadratic Objective Function
Ta Huu Phuong
Pages: 468-474
DOI: 10.1145/321958.321968
This paper presents a branch and bound method for solving problems in which the objective function is quadratic, the constraints are linear, and some or all variables are required to be integer. The algorithm is obtained by grafting an...

Linear Programming Computational Procedures for Ordinal Regression
V. Srinivasan
Pages: 475-487
DOI: 10.1145/321958.321969
The ordinal regression problem is an extension to the standard multiple regression problem in terms of assuming only ordinal properties for the dependent variable (rank order of preferred brands in a product class, academic ranks for students in...

Optimal Code Generation for Expression Trees
A. V. Aho, S. C. Johnson
Pages: 488-501
DOI: 10.1145/321958.321970
This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic...

Code Generation for a One-Register Machine
John Bruno, Ravi Sethi
Pages: 502-510
DOI: 10.1145/321958.321971
The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise...

Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars
M. D. Mickunas, R. L. Lancaster, V. B. Schneider
Pages: 511-533
DOI: 10.1145/321958.321972
A method is presented for directly transforming an arbitrary LR(k) grammar to an equivalent LR(1) grammar. It is further shown that the method transforms an arbitrary prefix-free LR(k) grammar to an equivalent...

Restructuring of Arithmetic Expressions For Parallel Evaluation
David E. Muller, Franco P. Preparata
Pages: 534-543
DOI: 10.1145/321958.321973
Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these...

On the complexity of edge traversing
Christos H. Papadimitriou
Pages: 544-554
DOI: 10.1145/321958.321974
It is shown that the Chinese Postman Problem, although tractable in the totally directed and the totally undirected cases, is NP-complete in the mixed case. A simpler version of the same problem is shown algorithmically equivalent to the...

P-Complete Approximation Problems
Sartaj Sahni, Teofilo Gonzalez
Pages: 555-565
DOI: 10.1145/321958.321975
For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these...

Lower Bounds on Merging Networks
Andrew Chi-Chih Yao, Foong Frances Yao
Pages: 566-571
DOI: 10.1145/321958.321976
Let M(m, n) be the minimum number or comparators needed in an (m, n)-merging network. It is shown that M(m, n) ≥ n(lg(m +...

Errata: `` Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices''
R. A. Cody, E. G. Coffman, Jr.
Page: 572
DOI: 10.1145/321958.321977