ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 32 Issue 4, Oct. 1985

A sufficient condition for backtrack-bounded search
Eugene C. Freuder
Pages: 755-761
DOI: 10.1145/4221.4225
Backtrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This...

A fast parallel algorithm for the maximal independent set problem
Richard M. Karp, Avi Wigderson
Pages: 762-773
DOI: 10.1145/4221.4226
A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm...

Closures of database hypergraphs
Domenico Saccà
Pages: 774-803
DOI: 10.1145/4221.4997
A hypergraph formalism is introduced to represent database schemata. In particular, a database schema B, described by one full join dependency and a set of functional dependencies, is represented by a (database) hypergraph...

Complexity of network synchronization
Baruch Awerbuch
Pages: 804-823
DOI: 10.1145/4221.4227
The problem of simulating a synchronous network by an asynchronous network is investigated. A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in...

Asynchronous consensus and broadcast protocols
Gabriel Bracha, Sam Toueg
Pages: 824-840
DOI: 10.1145/4221.214134
A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can...

How to assign votes in a distributed system
Hector Garcia-Molina, Daniel Barbara
Pages: 841-860
DOI: 10.1145/4221.4223
In a distributed system, one strategy for achieving mutual exclusion of groups of nodes without communication is to assign to each node a number of votes. Only a group with a majority of votes can execute the critical operations, and mutual...

On ordered languages and the optimization of linear functions by greedy algorithms
Ulrich Faigle
Pages: 861-870
DOI: 10.1145/4221.4998
The optimization problem for linear functions on finite languages is studied, and an (almost) complete characterization of those functions for which a primal and a dual greedy algorithm work well with respect to a canonically associated linear...

A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
Ilan Adler, Nimrod Megiddo
Pages: 871-895
DOI: 10.1145/4221.4222
It has been a challenge for mathematicians to confirm theoretically the extremely good performance of simplex-type algorithms for linear programming. In this paper the average number of steps performed by a simplex algorithm, the so-called...

Acceptance trees
M. Hennessy
Pages: 896-928
DOI: 10.1145/4221.4249
A simple model, AT, for nondeterministic machines is presented which is based on certain types of trees. A set of operations, &Sgr;, is defined over AT and it is shown to be completely characterized by a set of inequations over &Sgr;. AT is used...

Lower bounds for solving linear diophantine equations on random access machines
Friedhelm Meyer auf der Heide
Pages: 929-937
DOI: 10.1145/4221.4250
The problem of recognizing the language Ln(Ln, k) of solvable Diophantine linear equations with n variables (and solutions from {O, … ,...

Applications of Ramsey's theorem to decision tree complexity
Shlomo Moran, Marc Snir, Udi Manber
Pages: 938-949
DOI: 10.1145/4221.4259
Combinatorial techniques for extending lower bound results for decision trees to general types of queries are presented. Problems that are defined by simple inequalities between inputs, called order invariant problems, are...

A polynomial algorithm for the min-cut linear arrangement of trees
Mihalis Yannakakis
Pages: 950-988
DOI: 10.1145/4221.4228
An algorithm is presented that finds a min-cut linear arrangement of a tree in O(n log n) time. An extension of the algorithm determines the number of pebbles needed to play the black and white...