Journal of the ACM -- 1997

Volume 44, Number 1, January 1997

Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. Journal of the ACM, 44(1):1-29, January 1997. Abstract, References, etc. [BibTeX entry]
Serge Abiteboul, Moshe Y. Vardi, and Victor Vianu. Fixpoint logics, relational machines, and computational complexity. Journal of the ACM, 44(1):30-56, January 1997. Abstract, References, Citations, etc. [BibTeX entry]
Shinichi Morishita. Avoiding Cartesian products for multiple joins. Journal of the ACM, 44(1):57-85, January 1997. Abstract, References, Citations, etc. [BibTeX entry]
Baruch Awerbuch and Leonard J. Schulman. The maintenance of common data in a distributed system. Journal of the ACM, 44(1):86-103, January 1997. Abstract, References, etc. [BibTeX entry]
Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, and Eric J. Schwabe. Work-preserving emulations of fixed-connection networks. Journal of the ACM, 44(1):104-147, January 1997. Abstract, References, Citations, etc. [BibTeX entry]
Alexander T. Ishii, Charles E. Leiserson, and Marios C. Papaefthymiou. Optimizing two-phase, level-clocked circuitry. Journal of the ACM, 44(1):148-199, January 1997. Abstract, References, etc. [BibTeX entry]

Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization. Journal of the ACM, 44(2):201-236, March 1997. References. [BibTeX entry]
Tao Jiang, Joel I. Seiferas, and Paul M. B. Vitányi. Two heads are better than two tapes. Journal of the ACM, 44(2):237-256, March 1997. References, Citations, etc. [BibTeX entry]
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. Journal of the ACM, 44(2):257-271, March 1997. References, Citations, etc. [BibTeX entry]
Jan Van den Bussche, Dirk Van Gucht, Marc Andries, and Marc Gyssens. On the completeness of object-creating database transformation languages. Journal of the ACM, 44(2):272-319, March 1997. References, Citations, etc. [BibTeX entry]
W. Bibel and E. Eder. Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution. Journal of the ACM, 44(2):320-344, March 1997. References. [BibTeX entry]
Robert A. Wagner. Evaluating uniform expressions within two steps of minimum parallel time. Journal of the ACM, 44(2):345-361, March 1997. References. [BibTeX entry]

Joe Halpern. On becoming editor-in-chief of JACM. Journal of the ACM, 44(3):363-365, May 1997. [BibTeX entry]
Zhen Liu, Philippe Nain, and Don Towsley. Exponential bounds with applications to call admission. Journal of the ACM, 44(3):366-394, May 1997. Additional information. [BibTeX entry]
Rolf H. Möhring, Matthias Müller-Hannemann, and Karsten Weihe. Mesh refinement via bidrected flows: Modeling, complexity, and computational results. Journal of the ACM, 44(3):395-426, May 1997. References, etc. [BibTeX entry]
Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427-485, May 1997. References, Citations, etc. [BibTeX entry]
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3):486-504, May 1997. References, etc. [BibTeX entry]
R. Sekar, I. V. Ramakrishnan, and P. Mishra. On the power and limitations of strictness analysis. Journal of the ACM, 44(3):505-525, May 1997. References, etc. [BibTeX entry]

Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. Journal of the ACM, 44(4):527-548, July 1997. References, etc. [BibTeX entry]
Peter van Beek and Rina Dechter. Constraint tightness and looseness versus local and global consistency. Journal of the ACM, 44(4):549-566, July 1997. References, etc. [BibTeX entry]
Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, and Kasturi R. Varadarajan. Approximating shortest paths on a convex polytope in three dimensions. Journal of the ACM, 44(4):567-584, July 1997. References, Citations, etc. [BibTeX entry]
Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, July 1997. References, etc. [BibTeX entry]
Prasad Jayanti. Robust wait-free hierarchies. Journal of the ACM, 44(4):592-614, July 1997. References, etc. [BibTeX entry]
Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44(4):616-631, July 1997. References, etc. [BibTeX entry]
Tao Jiang, Joel I. Seiferas, and Paul M. B. Vitányi. Erratum: ``Two heads are better than two tapes''. Journal of the ACM, 44(4):632, July 1997. References. [BibTeX entry]

Ronen I. Brafman, Jean-Claude Latombe, Yoram Moses, and Yoav Shoham. Applications of a logic of knowledge to motion planning under uncertainty. Journal of the ACM, 44(5):633-668, September 1997. References, etc. [BibTeX entry]
David Eppstein, Zvi Galil, and Amnon Nissenzweig. Sparsification -- a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, September 1997. References, etc. [BibTeX entry]
Roni Khardon and Dan Roth. Learning to reason. Journal of the ACM, 44(5):697-725, September 1997. References, etc. [BibTeX entry]
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, and Eli Upfal. How much can hardware help routing? Journal of the ACM, 44(5):726-741, September 1997. References, Citations, etc. [BibTeX entry]
Thomas H. Spencer. Time-work tradeoffs for parallel algorithms. Journal of the ACM, 44(5):742-778, September 1997. References, etc. [BibTeX entry]

Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. Journal of the ACM, 44(6):779-805, November 1997. References, etc. [BibTeX entry]
Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörge Rothe. Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. Journal of the ACM, 44(6):806-825, November 1997. References, etc. [BibTeX entry]
Hal Wasserman and Manuel Blum. Software reliability via run-time result-checking. Journal of the ACM, 44(6):826-849, November 1997. References, etc. [BibTeX entry]
Manfred Broy. Compositional refinement of interactive systems. Journal of the ACM, 44(6):850-891, November 1997. References, etc. [BibTeX entry]