**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,...