Journal of the ACM, Volume 35, 1988

Volume 35, Number 1, January 1988

• Christoph Walther:
  Many-sorted unification. 1-17
  
• Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
  The complexity of searching a graph. 18-44
  
• Yann-Hang Lee, Kang G. Shin:
  Optimal design and use of retry in fault-tolerant computer systems. 45-69
  
• Serge Abiteboul, Victor Vianu:
  Equivalence and optimization of relational transactions. 70-120
  
• Vassos Hadzilacos:
  A theory of reliability in database systems. 121-145
  
• Anthony C. Klug:
  On conjunctive queries containing inequalities. 146-160
  
• Gaston H. Gonnet, Per-Åke Larson:
  External hashing with limited internal storage. 161-184
  
• Timothy J. Hickey, Jacques Cohen:
  Automating program analysis. 185-220
  
• Satish K. Tripathi, C. Murray Woodside:
  A vertex-allocation theorem for resources in queuing networks. 221-230
  
• Erich Kaltofen:
  Greatest common divisors of polynomials given by straight-line programs. 231-264
  

Volume 35, Number 2, April 1988

• Avikam Baltsan, Micha Sharir:
  On the shortest paths between two convex polyhedra. 267-287
  
• Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer:
  Consensus in the presence of partial synchrony. 288-323
  
• Robert McNaughton, Paliath Narendran, Friedrich Otto:
  Church-Rosser Thue systems and formal languages. 324-344
  
• Jeffrey D. Ullman, Allen Van Gelder:
  Efficient tests for top-down termination of logical rules. 345-373
  
• Zvi Galil, Éva Tardos:
  An O(n²(m + n log n)log n) min-cost flow algorithm. 374-386
  
• Galen H. Sasaki, Bruce Hajek:
  The time complexity of maximum matching by simulated annealing. 387-403
  
• Ravi S. Sandhu:
  The schematic protection model: its definition and analysis for acyclic attenuating schemes. 404-432
  
• A. Robert Calderbank, Edward G. Coffman Jr., Leopold Flatto:
  Optimal directory placement on disk storage devices. 433-446
  
• Helmut Alt:
  Comparing the combinational complexities of arithmetic functions. 447-460
  
• Ingo Wegener:
  On the complexity of branching programs and decision trees for clique functions. 461-471
  

Volume 35, Number 3, July 1988

• Natarajan Shankar:
  A mechanical proof of the Church-Rosser theorem. 475-522
  
• Merrick L. Furst, Jonathan L. Gross, Lyle A. McGeoch:
  Finding a maximum-genus graph imbedding. 523-534
  
• Wen-Lian Hsu:
  The coloring and maximum independent set problems on planar perfect graphs. 535-563
  
• Wansoo T. Rhee, Michel Talagrand:
  Some distributions that allow perfect packing. 564-578
  
• Jonathan Goodman, Albert G. Greenberg, Neal Madras, Peter March:
  Stability of binary exponential backoff. 579-602
  
• Lenwood S. Heath, Arnold L. Rosenberg, Bruce T. Smith:
  The physical mapping problem for parallel architectures. 603-634
  
• S. Rao Kosaraju, Mikhail J. Atallah:
  Optimal simulations between mesh-connected arrays of processors. 635-650
  
• Faith E. Fich, Martin Tompa:
  The parallel complexity of exponentiating polynomials over finite fields. 651-667
  
• Hans Daduna:
  Busy periods for subnetworks in stochastic networks: mean value analysis. 668-674
  
• Jan Robin Rohlicek, Alan S. Willsky:
  The reduction of perturbed Markov generators: an algorithm exposing the role of transient states. 675-696
  
• Jik H. Chang, Oscar H. Ibarra, Anastasios Vergis:
  On the power of one-way communication. 697-726
  
• Michael R. Fellows, Michael A. Langston:
  Nonconstructive tools for proving polynomial-time decidability. 727-739
  
• Friedhelm Meyer auf der Heide:
  Fast algorithms for N-dimensional restrictions of hard problems. 740-747
  
• Arnold Schönhage:
  A nonlinear lower bound for random-access machines under logarithmic cost. 748-754
  

Volume 35, Number 4, October 1988

• Vasek Chvátal, Endre Szemerédi:
  Many Hard Examples for Resolution. 759-768
  
• Michael D. Grigoriadis, B. Kalantari:
  A new class of heuristic algorithms for weighted perfect matching. 769-776
  
• Richard Cole, Alan Siegel:
  Optimal VLSI circuits for sorting. 777-809
  
• Teofilo F. Gonzalez, Sing-Ling Lee:
  A linear time algorithm for optimal routing around a rectangle. 810-831
  
• Shivendra S. Panwar, Donald F. Towsley, Jack K. Wolf:
  Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service. 832-844
  
• Hagit Attiya, Marc Snir, Manfred K. Warmuth:
  Computing on an anonymous ring. 845-875
  
• Anna R. Karlin, Eli Upfal:
  Parallel hashing: an efficient implementation of shared memory. 876-892
  
• Lyle Ramshaw:
  Eliminating go to's while preserving program structure. 893-920
  
• Andrew V. Goldberg, Robert Endre Tarjan:
  A new approach to the maximum-flow problem. 921-940
  
• David A. Mix Barrington, Denis Thérien:
  Finite monoids and the fine structure of NC¹. 941-952
  
• Daniel Leivant, Tim Fernando:
  Meager and replete failures of relative completeness. 953-964
  
• Leonard Pitt, Leslie G. Valiant:
  Computational limitations on learning from examples. 965-984
  
• Joel I. Seiferas, Paul M. B. Vitányi:
  Counting is easy. 985-1000
  
• Bruce Jay Collings, G. Barry Hembree: Addendum to ``Initializing Generalized Feedback Shift Register Pseudorandom Number Generators''. 1001