**An Efficient Algorithm for Finding an Irredundant Set Cover**

Charles R. Kime, Ramachendra P. Batni, Jeffrey D. Russell

Pages: 351-355

DOI: 10.1145/321832.321833

The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an m × n cover table, the execution time of the procedure is, in the worst case,...

**The Diclique Representation and Decomposition of Binary Relations**

Robert M. Haralick

Pages: 356-366

DOI: 10.1145/321832.321834

The binary relation is often a useful mathematical structure for representing simple relationships whose essence is a directed connection. To better aid in interpreting or storing a binary relation we suggest a diclique decomposition. A diclique...

**Characterizations of Reducible Flow Graphs**

M. S. Hecht, J. D. Ullman

Pages: 367-375

DOI: 10.1145/321832.321835

It is established that if G is a reducible flow graph, then edge (n, m) is backward (a back latch) if and only if either n = m or m dominates n in...

**Efficiency of a Binary Comparison Storage Technique**

E. M. Palmer, M. A. Rahimi, R. W. Robinson

Pages: 376-384

DOI: 10.1145/321832.321836

The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of...

**An Algorithm for the Chromatic Number of a Graph**

Chung C. Wang

Pages: 385-391

DOI: 10.1145/321832.321837

Christofides' algorithm for finding the chromatic number of a graph is improved both in speed and memory space by using a depth-first search rule to search for a shortest path in a reduced subgraph tree.

**A Combinatorial Problem Related to Multimodule Memory Organizations**

C. K. Wong, Don Coppersmith

Pages: 392-402

DOI: 10.1145/321832.321838

This paper deals with a combinatorial minimization problem arising from studies on multimodule memory organizations. Instead of searching for an optimum solution, a particular solution is proposed and it is demonstrated that it is close to...

**Information-Theoretic Limitations of Formal Systems**

Gregory J. Chaitin

Pages: 403-424

DOI: 10.1145/321832.321839

An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time...

**On Almost Everywhere Complex Recursive Functions**

John Gill, Manuel Blum

Pages: 425-435

DOI: 10.1145/321832.321840

Let h be a recursive function. A partial recursive function &psgr; is i.o. (infinitely often) h-complex if every program for &psgr; requires more than...

**Iterated Limiting Recursion and the Program Minimization Problem**

L. K. Schubert

Pages: 436-445

DOI: 10.1145/321832.321841

The general problem of finding minimal programs realizing given “program descriptions” is considered, where program descriptions may be of finite or infinite length and may specify arbitrary program properties. The problem of finding...

**Context-Limited Grammars**

Thomas N. Hibbard

Pages: 446-453

DOI: 10.1145/321832.321842

A phrase structure grammar is called context-limited if there exists a partial ordering on its alphabet such that any letter on the left of any production is less than some letter on the right of the same production. It is...

**Computing a Subinterval of the Image**

Paul L. Richman

Pages: 454-458

DOI: 10.1145/321832.321843

The problem of computing a desired function value to within a prescribed tolerance can be formulated in the following two distinct ways: Formulation I: Given x and ∈ > 0, compute f(x) to within ∈....

**Application of the Diffusion Approximation to Queueing Networks II: Nonequilibrium Distributions and Applications to Computer Modeling**

Hisashi Kobayashi

Pages: 459-469

DOI: 10.1145/321832.321844

Quite often explicit information about the behavior of a queue over a fairly short period is wanted. This requires solving the nonequilibrium solution of the queue-length distribution, which is usually quite difficult mathematically. The first...

**Waiting Lines and Times in a System with Polling**

Alan G. Konheim, Bernd Meister

Pages: 470-490

DOI: 10.1145/321832.321845

A communication system consisting of a number of buffered input terminals connected to a computer by a single channel is analyzed. The terminals are polled in sequence and the data is removed from the terminal's buffer. When the buffer has been...

**Bounds for Some Functions Concerning Dynamic Storage Allocation**

J. M. Robson

Pages: 491-499

DOI: 10.1145/321832.321846

The amount of store necessary to operate a dynamic storage allocation system, subject to certain constraints, with no risk of breakdown due to storage fragmentation, is considered. Upper and lower bounds are given for this amount of store, both...

**Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem**

Mandell Bellmore, Saman Hong

Pages: 500-504

DOI: 10.1145/321832.321847

It is shown that the multisalesmen problem can be solved by solving the standard traveling salesman problem on an expanded graph. The expanded graph has m — 1 more nodes than the original graph where m is...

**An Algorithm for the Bounded Variable Integer Programming Problem**

L. E. Trotter, Jr., C. M. Shetty

Pages: 505-513

DOI: 10.1145/321832.321848

An algorithm is proposed for the bounded variable pure integer programming problem which treats general integer variables directly in an implicit enumeration procedure closely related to that advanced by Balas and Geoffrion for binary...

**Some New Bounds on the Condition Numbers of Optimally Scaled Matrices**

T. I. Fenner, G. Loizou

Pages: 514-524

DOI: 10.1145/321832.321849

New lower bounds on the minimal condition numbers of a matrix with respect to both one-sided and two-sided scaling by diagonal matrices are obtained. These bounds improve certain results obtained by F. L. Bauer.