Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 43 Issue 4, July 1996

A new approach to the minimum cut problem
David R. Karger, Clifford Stein
Pages: 601-640
DOI: 10.1145/234533.234534
This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized,...

Bounding errors introduced by clustering of customers in closed product-form queuing networks
William C. Cheng, Richard R. Muntz
Pages: 641-669
DOI: 10.1145/234533.234539
Product-form queuing network models have been widely used to model systems with shared resources such as computer systems (both centralized and distributed), communication networks, and flexible manufacturing systems. Closed multichain...

Complexity of Makanin's algorithm
Antoni Kościelski, Leszek Pacholski
Pages: 670-684
DOI: 10.1145/234533.234543
The exponent of periodicity is an important factor in estimates of complexity of word-unification algorithms. We prove that the exponent of periodicity of a minimal solution of a word equation is of order 21.07d, where...

The weakest failure detector for solving consensus
Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg
Pages: 685-722
DOI: 10.1145/234533.234549
We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In Chandra and Toueg [1996], it is shown that W, a failure detector that...

How to share concurrent wait-free variables
Ming Li, John Tromp, Paul M. B. Vitányi
Pages: 723-746
DOI: 10.1145/234533.234556
Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is...

On the Fourier spectrum of monotone functions
Nader H. Bshouty, Christino Tamon
Pages: 747-770
DOI: 10.1145/234533.234564