ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 35 Issue 4, Oct. 1988

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