Journal of the ACM -- 1988

Volume 35, Number 1, January 1988

• Christoph Walther. Many-sorted unification. Journal of the ACM, 35(1):1-17, January 1988. Citations. [BibTeX entry]

• N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou. The complexity of searching a graph. Journal of the ACM, 35(1):18-44, January 1988. Citations. [BibTeX entry]

• Yann-Hang Lee and Kang G. Shin. Optimal design and use of retry in fault-tolerant computer systems. Journal of the ACM, 35(1):45-69, January 1988. [BibTeX entry]

• Serge Abiteboul and Victor Vianu. Equivalence and optimization of relational transactions. Journal of the ACM, 35(1):70-120, January 1988. Citations. [BibTeX entry]

• Vassos Hadzilacos. A theory of reliability in database systems. Journal of the ACM, 35(1):121-145, January 1988. Citations. [BibTeX entry]

• Anthony Klug. On conjunctive queries containing inequalities. Journal of the ACM, 35(1):146-160, January 1988. Citations. [BibTeX entry]

• Gaston H. Gonnet and Per-Åke Larson. External hashing with limited internal storage. Journal of the ACM, 35(1):161-184, January 1988. [BibTeX entry]

• Timothy Hickey and Jacques Cohen. Automating program analysis. Journal of the ACM, 35(1):185-220, January 1988. Citations. [BibTeX entry]

• Satish K. Tripathi and C. Murray Woodside. A vertex-allocation theorem for resources in queuing networks. Journal of the ACM, 35(1):221-230, January 1988. Citations. [BibTeX entry]

• Erich Kaltofen. Greatest common divisors of polynomials given by straight-line programs. Journal of the ACM, 35(1):231-264, January 1988. Citations. [BibTeX entry]

Volume 35, Number 2, April 1988

• Avikam Baltsan and Micha Sharir. On the shortest paths between two convex polyhedra. Journal of the ACM, 35(2):267-287, April 1988. Citations. [BibTeX entry]

• Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, April 1988. Citations. [BibTeX entry]

• Robert McNaughton, Paliath Narendran, and Friedrich Otto. Church-Rosser Thue systems and formal languages. Journal of the ACM, 35(2):324-344, April 1988. Citations. [BibTeX entry]

• Jeffrey D. Ullman and Allen Van Gelder. Efficient tests for top-down termination of logical rules. Journal of the ACM, 35(2):345-373, April 1988. Citations. [BibTeX entry]

• Zvi Galil and Éva Tardos. An O(n^2 (m + n log n)log n) min-cost flow algorithm. Journal of the ACM, 35(2):374-386, April 1988. Citations. [BibTeX entry]

• Galen H. Sasaki and Bruce Hajek. The time complexity of maximum matching by simulated annealing. Journal of the ACM, 35(2):387-403, April 1988. Citations. [BibTeX entry]

• Ravinderpal Singh Sandhu. The schematic protection model: Its definition and analysis for acyclic attenuating schemes. Journal of the ACM, 35(2):404-432, April 1988. [BibTeX entry]

• A. R. Calderbank, E. G. Coffman, Jr., and Leopold Flatto. Optimal directory placement on disk storage devices. Journal of the ACM, 35(2):433-446, April 1988. [BibTeX entry]

• Helmut Alt. Comparing the combinatorial complexities of arithmetic functions. Journal of the ACM, 35(2):447-460, April 1988. [BibTeX entry]

• Ingo Wegener. On the complexity of branching programs and decision trees for clique functions. Journal of the ACM, 35(2):461-471, April 1988. Citations. [BibTeX entry]

Volume 35, Number 3, July 1988

• N. Shankar. A mechanical proof of the Church-Rosser theorem. Journal of the ACM, 35(3):475-522, July 1988. [BibTeX entry]

• Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch. Finding a maximum-genus graph imbedding. Journal of the ACM, 35(3):523-534, July 1988. Citations. [BibTeX entry]

• Wen-Lian Hsu. The coloring and maximum independent set problems on planar perfect graphs. Journal of the ACM, 35(3):535-563, July 1988. [BibTeX entry]

• Wansoo T. Rhee and Michel Talagrand. Some distributions that allow perfect packing. Journal of the ACM, 35(3):564-578, July 1988. Citations. [BibTeX entry]

• Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March. Stability of binary exponential backoff. Journal of the ACM, 35(3):579-602, July 1988. Citations. [BibTeX entry]

• Lenwood S. Heath, Arnold L. Rosenberg, and Bruce T. Smith. The physical mapping problem for parallel architectures. Journal of the ACM, 35(3):603-634, July 1988. [BibTeX entry]

• S. Rao Kosaraju and Mikhail J. Atallah. Optimal simulations between mesh-connected arrays of processors. Journal of the ACM, 35(3):635-650, July 1988. Citations. [BibTeX entry]

• Faith E. Fich and Martin Tompa. The parallel complexity of exponentiating polynomials over finite fields. Journal of the ACM, 35(3):651-667, July 1988. Citations. [BibTeX entry]

• Hans Daduna. Busy periods for subnetworks in stochastic networks: Mean value analysis. Journal of the ACM, 35(3):668-674, July 1988. [BibTeX entry]

• Jan Robin Rohlicek and Alan S. Willsky. The reduction of perturbed Markov generators: An algorithm exposing the role of transient states. Journal of the ACM, 35(3):675-696, July 1988. [BibTeX entry]

• Jik H. Chang, Oscar H. Ibarra, and Anastasios Vergis. On the power of one-way communication. Journal of the ACM, 35(3):697-726, July 1988. Citations. [BibTeX entry]

• Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35(3):727-739, July 1988. Citations. [BibTeX entry]

• Friedhelm Meyer auf der Heide. Fast algorithms for N-dimensional restrictions of hard problems. Journal of the ACM, 35(3):740-747, July 1988. Citations. [BibTeX entry]

• Arnold Schönhage. A nonlinear lower bound for random-access machines under logarithmic cost. Journal of the ACM, 35(3):748-754, July 1988. Citations. [BibTeX entry]

Volume 35, Number 4, October 1988

• Va\v{s}ek Chvátal and Endre Szemerédi. Many hard examples for resolution. Journal of the ACM, 35(4):759-768, October 1988. Citations. [BibTeX entry]

• M. D. Grigoriadis and B. Kalantari. A new class of heuristic algorithms for weighed perfect matching. Journal of the ACM, 35(4):769-776, October 1988. [BibTeX entry]

• Richard Cole and Alan Siegel. Optimal VLSI circuits for sorting. Journal of the ACM, 35(4):777-809, October 1988. [BibTeX entry]

• Teofilo F. Gonzalez and Sing-Ling Lee. A linear time algorithm for optimal routing around a rectangle. Journal of the ACM, 35(4):810-831, October 1988. Citations. [BibTeX entry]

• Shivendra S. Panwar, Don Towsley, and Jack K. Wolf. Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service. Journal of the ACM, 35(4):832-844, October 1988. [BibTeX entry]

• Hagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an anonymous ring. Journal of the ACM, 35(4):845-875, October 1988. Citations. [BibTeX entry]

• Anna R. Karlin and Eli Upfal. Parallel hashing: An efficient implementation of shared memory. Journal of the ACM, 35(4):876-892, October 1988. Citations. [BibTeX entry]

• Lyle Ramshaw. Eliminating go to's while preserving program structure. Journal of the ACM, 35(4):893-920, October 1988. [BibTeX entry]

• Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, October 1988. Citations. [BibTeX entry]

• David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC^1. Journal of the ACM, 35(4):941-952, October 1988. Citations. [BibTeX entry]

• Daniel Leivant and Tim Fernando. Meager and replete failures of relative completeness. Journal of the ACM, 35(4):953-964, October 1988. [BibTeX entry]

• Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965-984, October 1988. Citations. [BibTeX entry]

• Joel I. Seiferas and Paul M. B. Vitányi. Counting is easy. Journal of the ACM, 35(4):985-1000, October 1988. Citations. [BibTeX entry]

• Bruce Jay Collings and G. Barry Hembree. Addendum to ``Initializing generalized feedback shift register pseudorandom number generators''. Journal of the ACM, 35(4):1001, October 1988. References. [BibTeX entry]

Shortcuts: