Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 44 Issue 1, Jan. 1997

Separators for sphere-packings and nearest neighbor graphs
Gary L. Miller, Shang-Hua Teng, William Thurston, Stephen A. Vavasis
Pages: 1-29
DOI: 10.1145/256292.256294
A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system...

Fixpoint logics, relational machines, and computational complexity
Serge Abiteboul, Moshe Y. Vardi, Victor Vianu
Pages: 30-56
DOI: 10.1145/256292.256295
We establish a general connection between fixpoint logic and complexity. On one side, we have fixpoint logic, parameterized by the choices of 1st-order operators (inflationary or noninflationary) and iteration constructs (deterministic,...

Avoiding Cartesian products for multiple joins
Shinichi Morishita
Pages: 57-85
DOI: 10.1145/256292.256296
Computing the natural join of a set of relations is an important operation in relational database systems. The ordering of joins determines to a large extent the computation time of the join. Since the number of possible orderings could be very...

The maintenance of common data in a distributed system
Baruch Awerbuch, Leonard J. Schulman
Pages: 86-103
DOI: 10.1145/256292.256298
A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and other purposes, of a record of the current...

Work-preserving emulations of fixed-connection networks
Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, Eric J. Schwabe
Pages: 104-147
DOI: 10.1145/256292.256299

Optimizing two-phase, level-clocked circuitry
Alexander T. Ishii, Charles E. Leiserson, Marios C. Papaefthymiou
Pages: 148-199
DOI: 10.1145/256292.256301