Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 41 Issue 5, Sept. 1994

Circumscription with homomorphisms: solving the equality and counterexample problems
Peter K. Rathmann, Marianne Winslett, Mark Manasse
Pages: 819-873
DOI: 10.1145/185675.185678
One important facet of common-sense reasoning is the ability to draw default conclusions about the state of the world, so that one can, for example, assume that a given bird flies in the absence of information to the contrary. A deficiency in...

The turn model for adaptive routing
Christopher J. Glass, Lionel M. Ni
Pages: 874-902
DOI: 10.1145/185675.185682

Equivalence, reversibility, symmetry and concavity properties in fork-join queuing networks with blocking
Yves Dallery, Zhen Liu, Don Towsley
Pages: 903-942
DOI: 10.1145/185675.185776
In this paper, we study quantitative as well as qualitative properties of Fork-Join Queuing Networks with Blocking (FJQN/Bs). Specifically, we prove results regarding the equivalence of the behavior of a FJQN/B and that of its duals and a...

Fully persistent lists with catenation
James R. Driscoll, Daniel D. K. Sleator, Robert E. Tarjan
Pages: 943-959
DOI: 10.1145/185675.185791
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A...

On the hardness of approximating minimization problems
Carsten Lund, Mihalis Yannakakis
Pages: 960-981
DOI: 10.1145/185675.306789

Shortest paths in the plane with polygonal obstacles
James A. Storer, John H. Reif
Pages: 982-1012
DOI: 10.1145/185675.185795
We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two...

A single-exponential upper bound for finding shortest paths in three dimensions
John H. Reif, James A. Storer
Pages: 1013-1019
DOI: 10.1145/185675.185811
We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required...

Counting networks
James Aspnes, Maurice Herlihy, Nir Shavit
Pages: 1020-1048
DOI: 10.1145/185675.185815
Many fundamental multi-processor coordination problems can be expressed as counting problems: Processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an...