Theory
Advertisement
GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
Given a pair of directed line graphs, the problem of ascertaining whether or not they are isomorphic is one for which no efficient algorithmic solution is known. Since a straightforward enumerative algorithm might require 40 years of running time on a very high speed computer in order to compare two 15-node graphs, a more sophisticated approach seems called for. The situation is similar to that prevailing in areas such as game-playing and theorem-proving, where practical algorithms are unknown (for the interesting cases), but where various practical though only partially successful techniques are available. GIT—Graph Isomorphism Tester—incorporates a variety of processes that attempt to narrow down the search for an isomorphism, or to demonstrate that none exists. No one scheme is relied upon exclusively for a solution, and the program is designed to avoid excessive computation along fruitless lines. GIT has been written in the COMIT language and successfully tested on the IBM 7090.
Floating-point arithmetic with 84-bit numbers
A classic and straightforward technique is presented which is not limited to the size or type of number representation used or multiple precision arithmetic.
A comparative study has been made of a variety of numerical techniques for fitting experimental data of the decay type by forms involving the sums of exponentials. Statistical errors of the fitted parameters are also calculated. These methods have been applied to artificially-generated sets of data as well as to the results of experiments with radioactive tracers on both human and animal subjects. Results show that the values of the fitted parameters are very sensitive to variations in the fitting procedure. Therefore great care must be exercised in identifying such values with physical constants. Although the values of functions derived from these fitted parameters which can definitely be associated with physical entities are generally more stable under variations in the fitting techniques, error bounds can be so large that no great confidence can be placed even in them. It would therefore appear best to select a uniform technique both for running the experiments and for analyzing the data, and then to consider as significant only relative results between one subject and the next.
A note on multiplying boolean matrices II
In a note by Baker [1], a method is given for getting the limiting connectivity matrix, B, of a matrix whose entries are Boolean 0's and 1's. Harary [2] suggests determining An-1 since An-1 = An = ··· , where n is the order of the matrix. The purpose of this note is to give a method for determining An-1. The method is also applicable to finding the output matrix of a switching network as described in [3] and [4] where again An-1 = An = ··· , but A now has Boolean switching functions as entries instead of 0's and 1's.
An efficient composite formula for multidimensional quadrature
A (2s+1)-point, second-degree quadrature formula for integration over an s-dimensional hyper-rectangle is presented. All but one of the points lie on the surface with weights of opposite sign attached to points on opposite faces. When a large volume is subdivided into congruent rectangular subdivisions, only one point is required in each interior subdivision to achieve second-degree accuracy.
A fast procedure for generating normal random variables
A technique for generating normally distributed random numbers is described. It is faster than those currently in general use and is readily applicable to both binary and decimal computers.
An example in “significant-digit” arithmetic
Different methods of handling the summing process for the geometric series are shown to give results indicating widely differing significances when carried out in a machine incorporating “significant-digit” arithmetic.
Use of the disk file on stretch
The paper begins by briefly describing the Stretch (IBM 7030) computer with special emphasis given to the organization and operation of its input-output equipment. Physical characteristics of the two-disk system (4,194,304 72-bit words, 8 µsec-per-word transmission rate, etc.) are noted. Timing limitations due to arm motion and disk rotation are discussed.
Applications of disk usage are discussed separately for problem programs and for systems programs such as compilers and the supervisory program. Approximately 260,000 words of disk storage are reserved for the storage of systems programs and the subroutine library. Problem programs, however, are not currently filed on the disk.
Certain programming techniques are discussed for transmitting words between disk and core storage with minimum delaying and interruption of the arithmetic unit. Dumps on disk are considered for both recovery from computer malfunction and for mathematical or physical developments during the calculation.
Partioning algorithms for finite sets
The partitions of a set with n elements are represented by certain n-tuples of positive integers. Algorithms are described which generate without repetitions the n-tuples corresponding to: (1) all partitions of the given set, (2) all partitions of the given set into m or fewer sets (1 ≨ m ≨ n), and (3) all partitions of the given set into exactly m sets (1 ≨ m ≨ n).
An extension of Fibonaccian search to several variables
A technique which uses Fibonaccion search concepts has been developed to solve optimization problems involving unimodal functions of several variables. The technique has not been proven to be optimal in the sense that the one-dimensional Fibonaccion search is. However, it is valuable for certain kinds of calculations.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More