Journal of the ACM -- 1985

Volume 32, Number 1, January 1985

• A. Bagchi and A. Mahanti. Three approaches to heuristic search in networks. Journal of the ACM, 32(1):1-27, January 1985. [BibTeX entry]

• A. Mahanti and A. Bagchi. AND/OR graph heuristic search methods. Journal of the ACM, 32(1):28-51, January 1985. Citations. [BibTeX entry]

• Leslie Lamport and P. M. Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM, 32(1):52-78, January 1985. Citations. [BibTeX entry]

• Serge Abiteboul. Disaggregations in databases. Journal of the ACM, 32(1):79-101, January 1985. [BibTeX entry]

• Ken Fuchs and Dennis Kafura. Memory-constrained task scheduling on a network of dual processors. Journal of the ACM, 32(1):102-129, January 1985. [BibTeX entry]

• Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, January 1985. Citations. [BibTeX entry]

• Matthew Hennessy and Robin Milner. Algebraic laws for nondeterminism and concurrency. Journal of the ACM, 32(1):137-161, January 1985. Citations. [BibTeX entry]

• Hendrik Vantilborgh. Aggregation with an error of O(epsilon^2). Journal of the ACM, 32(1):162-190, January 1985. [BibTeX entry]

• Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM, 32(1):191-204, January 1985. Citations. [BibTeX entry]

• Shimon Even, Alan L. Selman, and Yacov Yacobi. Hard-core theorems for complexity classes. Journal of the ACM, 32(1):205-217, January 1985. Citations. [BibTeX entry]

• Maria M. Klawe. A tight bound for black and white pebbles on the pyramid. Journal of the ACM, 32(1):218-228, January 1985. [BibTeX entry]

• J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. Journal of the ACM, 32(1):229-246, January 1985. Citations. [BibTeX entry]

Volume 32, Number 2, April 1985

• M. A. Bauer. Soundness and completeness of a synthesis algorithm based on example computations. Journal of the ACM, 32(2):249-279, April 1985. [BibTeX entry]

• G. Gottlob and A. Leitsch. On the efficiency of subsumption algorithms. Journal of the ACM, 32(2):280-295, April 1985. [BibTeX entry]

• Ching-Chy Wang, Errol L. LLoyd, and Mary Lou Soffa. Feedback vertex sets and cyclically reducible graphs. Journal of the ACM, 32(2):296-313, April 1985. [BibTeX entry]

• G. N. Buckley and A. Silberschatz. Beyond two-phase locking. Journal of the ACM, 32(2):314-326, April 1985. [BibTeX entry]

• Brenda S. Baker, Edward G. Coffman, Jr., and Dan E. Willard. Algorithms for resolving conflicts in dynamic storage allocation. Journal of the ACM, 32(2):327-343, April 1985. Citations. [BibTeX entry]

• M. E. Gonzalez Smith and J. A. Storer. Parallel algorithms for data compression. Journal of the ACM, 32(2):344-373, April 1985. Citations. [BibTeX entry]

• Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985. Citations. [BibTeX entry]

• G. Cornuéjols, D. Naddef, and W. Pulleyblank. The traveling salesman problem in graphs with 3-edge cutsets. Journal of the ACM, 32(2):383-410, April 1985. [BibTeX entry]

• John Staples and V. L. Nguyen. A fixpoint semantics for nondeterministic data flow. Journal of the ACM, 32(2):411-444, April 1985. Citations. [BibTeX entry]

• Asser N. Tantawi and Don Towsley. Optimal static load balancing in distributed computer systems. Journal of the ACM, 32(2):445-465, April 1985. Citations. [BibTeX entry]

• Eitan M. Gurari. Decidable problems for powerful programs. Journal of the ACM, 32(2):466-483, April 1985. [BibTeX entry]

• S. Skyum and L. G. Valiant. A complexity theory based on Boolean algebra. Journal of the ACM, 32(2):484-502, April 1985. Citations. [BibTeX entry]

Volume 32, Number 3, July 1985

• Rina Dechter and Judea Pearl. Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3):505-536, July 1985. Citations. [BibTeX entry]

• Edward A. Bender and Jon T. Butler. Enumeration of structured flowcharts. Journal of the ACM, 32(3):537-548, July 1985. [BibTeX entry]

• William H. Cunningham. Optimal attach and reinforcement of a network. Journal of the ACM, 32(3):549-561, July 1985. Citations. [BibTeX entry]

• C. C. Lee and D. T. Lee. A simple on-line bin-packing algorithm. Journal of the ACM, 32(3):562-572, July 1985. Citations. [BibTeX entry]

• Bernard Chazelle and Louis Monier. A model of computation for VLSI with related complexity results. Journal of the ACM, 32(3):573-588, July 1985. Citations. [BibTeX entry]

• Albert G. Greenberg and Shmuel Winograd. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. Journal of the ACM, 32(3):589-596, July 1985. Citations. [BibTeX entry]

• Dan E. Willard and George S. Lueker. Adding range restriction capability to dynamic data structures. Journal of the ACM, 32(3):597-617, July 1985. Citations. [BibTeX entry]

• Y. C. Tay, Rajan Suri, and Nathan Goodman. A mean value performance model for locking in databases: The no-waiting case. Journal of the ACM, 32(3):618-651, July 1985. Citations. [BibTeX entry]

• Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652-686, July 1985. Citations. [BibTeX entry]

• Andrew C. Yao. Uniform hashing is optimal. Journal of the ACM, 32(3):687-693, July 1985. Citations. [BibTeX entry]

• David Zerling. Generating binary trees using rotations. Journal of the ACM, 32(3):694-701, July 1985. Citations. [BibTeX entry]

• Wei-Lu Cao and William J. Stewart. Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains. Journal of the ACM, 32(3):702-719, July 1985. [BibTeX entry]

• Udi Manber and Martin Tompa. The complexity of problems on probabilistic nondeterministic, and alternating decision trees. Journal of the ACM, 32(3):720-732, July 1985. [BibTeX entry]

• A. P. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. Journal of the ACM, 32(3):733-749, July 1985. Citations. [BibTeX entry]

• Christos H. Papadimitriou. Correction to ``A theorem in database concurrency control''. Journal of the ACM, 32(3):750, July 1985. References. [BibTeX entry]

Volume 32, Number 4, October 1985

• Eugene C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4):755-761, October 1985. Citations. [BibTeX entry]

• Richard M. Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4):762-773, October 1985. Citations. [BibTeX entry]

• Domenico Saccà. Closures of database hypergraphs. Journal of the ACM, 32(4):774-803, October 1985. [BibTeX entry]

• Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, October 1985. Citations. [BibTeX entry]

• Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM, 32(4):824-840, October 1985. Citations. [BibTeX entry]

• Hector Garcia-Molina and Daniel Barbara. How to assign votes in a distributed system. Journal of the ACM, 32(4):841-860, October 1985. Citations. [BibTeX entry]

• Ulrich Faigle. On ordered languages and the optimization of linear functions by greedy algorithms. Journal of the ACM, 32(4):861-870, October 1985. [BibTeX entry]

• Ilan Adler and Nimrod Megiddo. A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension. Journal of the ACM, 32(4):871-895, October 1985. Citations. [BibTeX entry]

• M. Hennessy. Acceptance trees. Journal of the ACM, 32(4):896-928, October 1985. Citations. [BibTeX entry]

• Friedhelm Meyer auf der Heide. Lower bounds for solving linear Diophantine equations on random access machines. Journal of the ACM, 32(4):929-937, October 1985. Citations. [BibTeX entry]

• Shlomo Moran, Marc Snir, and Udi Manber. Applications of Ramsey's theorem to decision tree complexity. Journal of the ACM, 32(4):938-949, October 1985. Citations. [BibTeX entry]

• Mihalis Yannakakis. A polynomial algorithm for the min-cut linear arrangement of trees. Journal of the ACM, 32(4):950-988, October 1985. Citations. [BibTeX entry]

Shortcuts: