**Many hard examples for resolution**

Vašek Chvátal, Endre Szemerédi

Pages: 759-768

DOI: 10.1145/48014.48016

For every choice of positive integers c and k such that k ≥ 3 and c2-k ≥ 0.7, there is a positive number &egr; such that, with...

**A new class of heuristic algorithms for weighted perfect matching**

M. D. Grigoriadis, B. Kalantari

Pages: 769-776

DOI: 10.1145/48014.48015

The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k ≤...

**Optimal VLSI circuits for sorting**

Richard Cole, Alan Siegel

Pages: 777-809

DOI: 10.1145/48014.48017

This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N2, for the standard...

**A linear time algorithm for optimal routing around a rectangle**

Teofilo F. Gonzalez, Sing-Ling Lee

Pages: 810-831

DOI: 10.1145/48014.48018

The problem of connecting a set of terminals that lie on the sides of a rectangle to minimize the total area is discussed. An O(n) algorithm is presented to solve this problem when the set of n...

**Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service**

Shivendra S. Panwar, Don Towsley, Jack K. Wolf

Pages: 832-844

DOI: 10.1145/48014.48019

Many problems can be modeled as single-server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time...

**Computing on an anonymous ring**

Hagit Attiya, Marc Snir, Manfred K. Warmuth

Pages: 845-875

DOI: 10.1145/48014.48247

The computational capabilities of a system of n indistinguishable (anonymous) processors arranged on a ring in the synchronous and asynchronous models of distributed computation are analyzed. A precise characterization of the...

**Parallel hashing**: an efficient implementation of shared memory

Anna R. Karlin, Eli Upfal

Pages: 876-892

DOI: 10.1145/48014.350550

**Eliminating go to's while preserving program structure**

Lyle Ramshaw

Pages: 893-920

DOI: 10.1145/48014.48021

Suppose we want to eliminate the local go to statements of a Pascal program by replacing them with multilevel loop exit statements. The standard ground rules for eliminating go to's require that we preserve the flow graph of the program, but...

**A new approach to the maximum-flow problem**

Andrew V. Goldberg, Robert E. Tarjan

Pages: 921-940

DOI: 10.1145/48014.61051

All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network...

**Finite monoids and the fine structure of NC1**

David A. Mix Barrington, Denis Thérien

Pages: 941-952

DOI: 10.1145/48014.63138

Recently a new connection was discovered between the parallel complexity class NC1 and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform)...

**Meager and replete failures of relative completeness**

Daniel Leivant, Tim Fernando

Pages: 953-964

DOI: 10.1145/48014.63139

The nature of programming languages that fail to have a relatively complete proof formalism is discussed. First, it is shown that such failures may be due to the meagerness of the programming language, rather than to the presence of complex...

**Computational limitations on learning from examples**

Leonard Pitt, Leslie G. Valiant

Pages: 965-984

DOI: 10.1145/48014.63140

The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes...

**Counting is easy**

Joel I. Seiferas, Paul M. B. Vitányi

Pages: 985-1000

DOI: 10.1145/48014.63141

For any fixed k, a remarkably simple single-tape Turing machine can simulate k independent counters in real time.