ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 20 Issue 3, July 1973

A Backtrack Procedure for Isomorphism of Directed Graphs
A. T. Berztiss
Pages: 365-377
DOI: 10.1145/321765.321766
A reasonably efficient procedure for testing pairs of directed graphs for isomorphism is important in information retrieval and other application fields in which structured data have to be matched. One such procedure, a backtrack procedure based...

A Path Entropy Function for Rooted Trees
Christopher D. Green
Pages: 378-384
DOI: 10.1145/321765.321767
The class of rooted trees or arborescences used for modeling hierarchical classification and indexing procedures is considered. An entropy function measuring the complexity of the paths from the root to the terminal vertices is defined. Upper...

A Note on Dijkstra's Shortest Path Algorithm
Donald B. Johnson
Pages: 385-388
DOI: 10.1145/321765.321768
An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O(n3) steps is disproved by showing a set of networks which take...

A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in N-Node Nonnegative-Distance Networks
Thomas A. Williams, Gregory P. White
Pages: 389-390
DOI: 10.1145/321765.321769
An error in Yen's algorithm is pointed out, and an alternative is offered which will produce correct results.

Reply to Williams and White's Note
Jin Y. Yen
Page: 390
DOI: 10.1145/321765.321770

On Local Roundoff Errors in Floating-Point Arithmetic
Toyohisa Kaneko, Bede Liu
Pages: 391-398
DOI: 10.1145/321765.321771
A bound on the relative error in floating-point addition using a single-precision accumulator with guard digits is derived. It is shown that even with a single guard digit, the accuracy can be almost as good as that using a double-precision...

Toward Abstract Numerical Analysis
Webb Miller
Pages: 399-408
DOI: 10.1145/321765.321772
This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function...

An Algorithm for the Inversion of Block Matrices of Toeplitz Form
G. A. Watson
Pages: 409-415
DOI: 10.1145/321765.321773
An algorithm of W. F. Trench is generalized to apply to the inversion of block matrices of Toeplitz form.

Cyclic Queues with Bulk Arrivals
Igal Adiri
Pages: 416-428
DOI: 10.1145/321765.321774
This paper deals with a single-server station (a computer) where each customer's demand comprises an independent random number of jobs (programs). Under certain assumptions, two cyclic disciplines are mathematically analyzed: (a) continuous job...

Placement of Records on a Secondary Storage Device to Minimize Access Time
David D. Grossman, Harvey F. Silverman
Pages: 429-438
DOI: 10.1145/321765.321775
The problem considered is how to place records on a secondary storage device to minimize average retrieval time, based on a knowledge of the probability for accessing the records. Theorems are presented for two limiting cases. A numerical...

Some Results in Computational Topology
G. Tourlakis, J. Mylopoulos
Pages: 439-455
DOI: 10.1145/321765.321776
It is the object of this paper to study the topological properties of finite graphs that can be embedded in the n-dimensional integral lattice (denoted Nn). The basic notion of deletability...

Generalized Feedback Shift Register Pseudorandom Number Algorithm
T. G. Lewis, W. H. Payne
Pages: 456-468
DOI: 10.1145/321765.321777
The generalized feedback shift register pseudorandom number algorithm has several advantages over all other pseudorandom number generators. These advantages are: (1) it produces multidimensional pseudorandom numbers; (2) it has an arbitrarily...

An Asymptotically Random Tausworthe Sequence
J. P. R. Tootill, W. D. Robinson, D. J. Eagle
Pages: 469-481
DOI: 10.1145/321765.321778
The theoretical limitations on the orders of equidistribution attainable by Tausworthe sequences are derived from first principles and are stated in the form of a criterion to be achieved. A second criterion, extending these limitations to...

Efficient Ordering of Set Expressions for Symbolic Expansion
R. B. Worrell, B. L. Hulme
Pages: 482-488
DOI: 10.1145/321765.321779
This paper gives an algorithm for efficiently ordering the terms and factors of a set (or Boolean) expression so that the work required for the symbolic expansion of the expression according to the distributive law is minimized. Formulas are...

Decidable Properties of Monadic Functional Schemas
Edward Ashcroft, Zohar Manna, Amir Pnueli
Pages: 489-499
DOI: 10.1145/321765.321780
A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to...

Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
Gideon Ehrlich
Pages: 500-513
DOI: 10.1145/321765.321781
The purpose of this work is to find a method for building loopless algorithms for listing combinatorial items, like partitions, permutations, combinations. Gray code, etc. Algorithms for the above sequence are detailed in full.

Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
Robert M. Keller
Pages: 514-537
DOI: 10.1145/321765.321782
The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part I presents the basic properties of this model. Two types of equivalence relation on computations are presented, to each of which...

Erratum: “An axiomatic approach to code optimization for expressions”
James C. Beatty
Page: 538
DOI: 10.1145/321765.321783