ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 23 Issue 1, Jan. 1976

Bounds on the Complexity of the Longest Common Subsequence Problem
J. D. Ullman, A. V. Aho, D. S. Hirschberg
Pages: 1-12
DOI: 10.1145/321921.321922
The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of...

Bounds for the String Editing Problem
C. K. Wong, Ashok K. Chandra
Pages: 13-16
DOI: 10.1145/321921.321923
The string editing problem is to determine the distance between two strings as measured by the minimal cost sequence of deletions, insertions, and changes of symbols needed to transform one string into the other. The longest common subsequence...

On the Complete Covering Problem for LR(k)Grammars
M. Dennis Mickunas
Pages: 17-30
DOI: 10.1145/321921.321924
A direct, one-step transformation is presented for transforming an arbitrary LR(k) context-free grammar, G, to an LR(1) grammar, G′, which completely...

An Algorithm for Subgraph Isomorphism
J. R. Ullmann
Pages: 31-42
DOI: 10.1145/321921.321925
Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess...

The Complexity of Near-Optimal Graph Coloring
M. R. Garey, D. S. Johnson
Pages: 43-49
DOI: 10.1145/321921.321926
Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and...

A Shortest Path Algorithm for Edge-Sparse Graphs
Robert A. Wagner
Pages: 50-57
DOI: 10.1145/321921.321927
An algorithm (FLOW) for finding the shortest distance from a given node S to each node X of a directed graph with nonnegative integer arc lengths less than or equal to WM is...

A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph
Alberto Martelli
Pages: 58-73
DOI: 10.1145/321921.321928
By defining a suitable algebra for cut sets, it is possible to reduce the problem of enumerating the cut sets between all pairs of nodes in a graph to the problem of solving a system of linear equations. An algorithm for solving this system...

Note on Hopcroft and Tarjan's Planarity Algorithm
Narsingh Deo
Pages: 74-75
DOI: 10.1145/321921.321929
Errata are given for “Efficient Planarity Testing” by John Hopcroft and Robert Tarjan [J. ACM 21, 4 (Oct. 1974), 549-568].

Precision Weighting—An Effective Automatic Indexing Method
C. T. Yu, G. Salton
Pages: 76-88
DOI: 10.1145/321921.321930
A great many automatic indexing methods have been implemented and evaluated over the last few years, and automatic procedures comparable in effectiveness to conventional manual ones are now easy to generate. Two drawbacks of the available...

Numerical Inversion of Laplace Transforms Using a Fourier Series Approximation
Kenny S. Crump
Pages: 89-96
DOI: 10.1145/321921.321931
A method is presented for numerically inverting a Laplace transform that requires, in addition to the transform function itself, only sine, cosine, and exponential functions. The method is conceptually much like the method of Dubner and Abate,...

Adaptive Allocation of Central Processing Unit Quanta
D. Potier, E. Gelenbe, J. Lenfant
Pages: 97-102
DOI: 10.1145/321921.321932
A method is presented for numerically inverting a Laplace transform that requires, in addition to the transform function itself, only sine, cosine, and exponential functions. The method is conceptually much like the method of Dubner and Abate,...

Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
R. A. Cody, E. G. Coffman, Jr.
Pages: 103-115
DOI: 10.1145/321921.321933
This paper examines the problem of distributing a set of equal-size records among the sectors of a drum-like storage device in order to exploit known access frequencies and reduce the average access time. A simple catenated search model is...

Algorithms for Scheduling Independent Tasks
Sartaj K. Sahni
Pages: 116-127
DOI: 10.1145/321921.321934
The following job sequencing problems are studied: (i) single processor job sequencing with deadlines, (ii) job sequencing on m-identical processors to minimize finish time and related problems, (iii) job sequencing on...

The independence of miss ratio on page size
Ronald Fagin, Malcolm C. Easton
Pages: 128-146
DOI: 10.1145/321921.321935
A theoretical justification is given to the empirical observation that in some computing systems with a paged, 2-level storage hierarchy, long-term miss ratio is roughly independent of page size. Let MISS be the expected...

A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
D. S. Hirschberg, C. K. Wong
Pages: 147-154
DOI: 10.1145/321921.321936
The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem...

A Code for the Transportation Problem of Linear Programming
Britton Harris
Pages: 155-157
DOI: 10.1145/321921.321937
Methods are described and results presented for greatly reducing the computation time for long narrow problems of the transportation problem of linear programming. The code builds on known methods with two principal innovations: a substantial...

Global Data Flow Analysis and Iterative Algorithms
John B. Kam, Jeffrey D. Ullman
Pages: 158-171
DOI: 10.1145/321921.321938
Kildall has developed data propagation algorithms for code optimization in a general lattice theoretic framework. In another direction, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms...

A Fast and Usually Linear Algorithm for Global Flow Analysis
Susan L. Graham, Mark Wegman
Pages: 172-202
DOI: 10.1145/321921.321939
A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst-case time bound of...

A Completeness Theorem for Straight-Line Programs with Structured Variables
Christoph M. Hoffmann, Lawrence H. Landweber
Pages: 203-220
DOI: 10.1145/321921.321940
A program scheme which models straight-line code admitting structured variables such as arrays, lists, and queues is considered. A set of expressions is associated with a program reflecting the input-output transformations. A basic set of axioms...