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