Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 1, Jan. 2000

The harmonic k-server algorithm is competitive
Yair Bartal, Eddie Grove
Pages: 1-15
DOI: 10.1145/331605.331606
The k-server problem is a generalization of the paging problems, and is the most studied problem in the area of competive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the...

Parallel RAMs with owned global memory and deterministic context-free language recognition
Patrick W. Dymond, Walter L. Ruzzo
Pages: 16-45
DOI: 10.1145/331605.331607
We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, Owner Write, or CROW-PRAMS, these are machines in which...

Minimum cuts in near-linear time
David R. Karger
Pages: 46-76
DOI: 10.1145/331605.331608
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling...

Existential second-order logic over strings
Thomas Eiter, Georg Gottlob, Yuri Gurevich
Pages: 77-131
DOI: 10.1145/331605.331609
Existential second-order logic (ESO) and monadic second-order logic(MSO) have attracted much interest in logic and computer science. ESO is a much expressive logic over successor structures than MSO. However, little was known about the...

Polylog-time and near-linear work approximation scheme for undirected shortest paths
Edith Cohen
Pages: 132-166
DOI: 10.1145/331605.331610
Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than...

From Algol to polymorphic linear lambda-calculus
Peter W. O'Hearn, John C. Reynolds
Pages: 167-223
DOI: 10.1145/331605.331611
In a linearly-typed functional language, one can define functions that consume their arguments in the process of computing their results. This is reminiscent of state transformations in imperative languages, where execition of an assignment...