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 2, April 1976

An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Harold N. Gabow
Pages: 221-234
DOI: 10.1145/321941.321942
A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching. The...

Efficiency of Computation of Cayley Tables of 2-Groups
Richard G. Larson
Pages: 235-241
DOI: 10.1145/321941.321943
Two algorithms for computing the multiplication table of a 2-group are described and discussed. One of the algorithms works in an element-by-element fashion; the other works in terms of subgroups generated by initial subsequences of the given...

Fast Multiple-Precision Evaluation of Elementary Functions
Richard P. Brent
Pages: 242-251
DOI: 10.1145/321941.321944
Let ƒ(x) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M(n) be the number of single-precision operations required to multiply n-bit...

New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
H. T. Kung
Pages: 252-261
DOI: 10.1145/321941.321945
The parallel evaluation of rational expressions is considered. New algorithms which minimize the number of multiplication or division steps are given. They are faster than the usual algorithms when multiplication or division takes more time than...

A Space-Economical Suffix Tree Construction Algorithm
Edward M. McCreight
Pages: 262-272
DOI: 10.1145/321941.321946
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in...

A Statistical Model for Relevance Feedback in Information Retrieval
C. T. Yu, W. S. Luk, T. Y. Cheung
Pages: 273-286
DOI: 10.1145/321941.321947
A statistical model is presented for the investigation of a practical method used in relevance feedback. A necessary and sufficient condition for the two parameters used in this method to define a better query than the original query is given. A...

Convergence Estimates for the Distribution of Trailing Digits
Alan Feldstein, Richard Goodman
Pages: 287-297
DOI: 10.1145/321941.321948
This paper analyzes the distribution of trailing digits (tail end digits) of positive real floating-point numbers represented in arbitrary base &bgr; and randomly chosen from a logarithmic distribution. The analysis shows that...

Array Permutation by Index-Digit Permutation
Donald Fraser
Pages: 298-309
DOI: 10.1145/321941.321949
An array may be reordered according to a common permutation of the digits of each of its element indices. The digit-reversed reordering which results from common fast Fourier transform (FFT) algorithms is an example. By examination of this class...

On the Linear Convergence of a Covariance Factorization Algorithm
Marcello Pagano
Pages: 310-316
DOI: 10.1145/321941.321950
An algorithm for factoring a covariance function into its Hurwitz factors, which is based on the Cholesky factors of a certain matrix, was proposed by F.L. Bauer and others. This algorithm bears a close connection to the theory of orthogonal...

Exact and Approximate Algorithms for Scheduling Nonidentical Processors
Ellis Horowitz, Sartaj Sahni
Pages: 317-327
DOI: 10.1145/321941.321951
Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and...

A Queueing Model with Finite Waiting Room and Blocking
Alan G. Konheim, Martin Reiser
Pages: 328-341
DOI: 10.1145/321941.321952
A two-stage queueing network with feedback and a finite intermediate waiting room is studied. The first-stage server is blocked whenever M requests are enqueued in the second stage. The analysis of this system under exponential...

A Note on the Effect or the Central Processor Service Time Distribution on Processor Utilization in Multiprogrammed Computer Systems
Thomas G. Price
Pages: 342-346
DOI: 10.1145/321941.321953
Upper and lower bounds on processor utilization for the queueing model M/G/1/N are derived. The upper bound is equal to the utilization for constant service times and the lower bound is approached when the average number of operations per busy...

Simulating Stable Stochastic Systems, VI: Quantile Estimation
Donald L. Iglehart
Pages: 347-360
DOI: 10.1145/321941.321954
In this paper the author continues his study of the regenerative method for analyzing simulations of stable stochastic systems. The principal concern is to estimate the quantiles of the stationary distribution of a regenerative process. Markov...

A Simple Approximation to the Average Queue Size in the Time-Dependent M/M/1 Queue
Kenneth Lloyd Rider
Pages: 361-367
DOI: 10.1145/321941.321955
The time-dependent equations for the M/M/1 queue can be reduced to a single equation for the expected queue size, but the equation is dependent on P0(t), the probability of no jobs in the...

Picture Segmentation by a Tree Traversal Algorithm
Steven L. Horowitz, Theodosios Pavlidis
Pages: 368-388
DOI: 10.1145/321941.321956
In the past, picture segmentation has been performed by merging small primitive regions or by recursively splitting the whole picture. This paper combines the two approaches with significant increase in processing speed while maintaining small...

Proving Properties of Complex Data Structures
Ben Wegbreit, Jay M. Spitzen
Pages: 389-396
DOI: 10.1145/321941.321957
This paper is concerned with proving properties of programs which use data structures. The goal is to be able to prove that all instances of a class (e.g. as defined in Simula) satisfy some property. A method of proof which achieves this goal,...