Journal of the ACM, Volume 23, 1976

Volume 23, Number 1, January 1976

• Alfred V. Aho, Daniel S. Hirschberg, Jeffrey D. Ullman:
  Bounds on the Complexity of the Longest Common Subsequence Problem. 1-12
  
• C. K. Wong, Ashok K. Chandra:
  Bounds for the String Editing Problem. 13-16
  
• M. Dennis Mickunas:
  On the Complete Covering Problem for LR(k)Grammars. 17-30
  
• Julian R. Ullmann:
  An Algorithm for Subgraph Isomorphism. 31-42
  
• M. R. Garey, David S. Johnson:
  The Complexity of Near-Optimal Graph Coloring. 43-49
  
• Robert A. Wagner:
  A Shortest Path Algorithm for Edge-Sparse Graphs. 50-57
  
• Alberto Martelli:
  A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph. 58-73
  
• Narsingh Deo:
  Note on Hopcroft and Tarjan's Planarity Algorithm. 74-75
  
• Clement T. Yu, Gerard Salton:
  Precision Weighting - An Effective Automatic Indexing Method. 76-88
  
• Kenny S. Crump:
  Numerical Inversion of Laplace Transforms Using a Fourier Series Approximation. 89-96
  
• Dominique Potier, Erol Gelenbe, Jacques Lenfant:
  Adaptive Allocation of Central Processing Unit Quanta. 97-102
  
• R. A. Cody, Edward G. Coffman Jr.:
  Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices. 103-115
  
• Sartaj Sahni:
  Algorithms for Scheduling Independent Tasks. 116-127
  
• Ronald Fagin, Malcolm C. Easton:
  The independence of miss ratio on page size. 128-146
  
• Daniel S. Hirschberg, C. K. Wong:
  A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables. 147-154
  
• Britton Harris:
  A Code for the Transportation Problem of Linear Programming. 155-157
  
• John B. Kam, Jeffrey D. Ullman:
  Global Data Flow Analysis and Iterative Algorithms. 158-171
  
• Susan L. Graham, Mark N. Wegman:
  A Fast and Usually Linear Algorithm for Global Flow Analysis. 172-202
  
• Christoph M. Hoffmann, Lawrence H. Landweber:
  A Completeness Theorem for Straight-Line Programs with Structured Variables. 203-220
  

Volume 23, Number 2, April 1976

• Harold N. Gabow:
  An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs. 221-234
  
• Richard G. Larson:
  Efficiency of Computation of Cayley Tables of 2-Groups. 235-241
  
• Richard P. Brent:
  Fast Multiple-Precision Evaluation of Elementary Functions. 242-251
  
• H. T. Kung:
  New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences. 252-261
  
• Edward M. McCreight:
  A Space-Economical Suffix Tree Construction Algorithm. 262-272
  
• Clement T. Yu, W. S. Luk, T. Y. Cheung:
  A Statistical Model for Relevance Feedback in Information Retrieval. 273-286
  
• Alan Feldstein, Richard Goodman:
  Convergence Estimates for the Distribution of Trailing Digits. 287-297
  
• Donald Fraser:
  Array Permutation by Index-Digit Permutation. 298-309
  
• Marcello Pagano:
  On the Linear Convergence of a Covariance Factorization Algorithm. 310-316
  
• Ellis Horowitz, Sartaj Sahni:
  Exact and Approximate Algorithms for Scheduling Nonidentical Processors. 317-327
  
• Alan G. Konheim, Martin Reiser:
  A Queueing Model with Finite Waiting Room and Blocking. 328-341
  
• Thomas G. Price:
  A Note on the Effect or the Central Processor Service Time Distribution on Processor Utilization in Multiprogrammed Computer Systems. 342-346
  
• Donald L. Iglehart:
  Simulating Stable Stochastic Systems, VI: Quantile Estimation. 347-360
  
• Kenneth Lloyd Rider:
  A Simple Approximation to the Average Queue Size in the Time-Dependent M/M/1 Queue. 361-367
  
• Steven L. Horowitz, Theodosios Pavlidis:
  Picture Segmentation by a Tree Traversal Algorithm. 368-388
  
• Ben Wegbreit, Jay M. Spitzen:
  Proving Properties of Complex Data Structures. 389-396
  

Volume 23, Number 3, July 1976

• Editor's Note. 397
• William H. Joyner Jr.:
  Resolution Strategies as Decision Procedures. 398-417
  
• Lena Chang, James F. Korsh:
  Canonical Coin Changing and Greedy Solutions. 418-422
  
• Nicholas Pippenger, Leslie G. Valiant:
  Shifting Graphs and Their Applications. 423-432
  
• Douglas C. Schmidt, Larry E. Druffel:
  A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices. 433-445
  
• Peter J. Slater:
  R-Domination in Graphs. 446-450
  
• William H. Burge:
  An Analysis of Binary Search Trees Formed from Sequences of Nondistinct Keys. 451-454
  
• Jeff R. Cash:
  Semi-Implicit Runge-Kutta Procedures with Error Estimates for the Numerical Integration of Stiff Systems of Ordinary Differential Equations. 455-460
  
• M. R. Garey, David S. Johnson:
  Scheduling Tasks with Nonuniform Deadlines on Two Processors. 461-467
  
• Ta Huu Phuong:
  Solution of Integer Programs with a Quadratic Objective Function. 468-474
  
• V. Srinivasan:
  Linear Programming Computational Procedures for Ordinal Regression. 475-487
  
• Alfred V. Aho, Stephen C. Johnson:
  Optimal Code Generation for Expression Trees. 488-501
  
• John L. Bruno, Ravi Sethi:
  Code Generation for a One-Register Machine. 502-510
  
• M. Dennis Mickunas, Ronald L. Lancaster, Victor B. Schneider:
  Transforming LR(k) Grammars to LR(1), SLR(1), and (1, 1) Bounded Right-Context Grammars. 511-533
  
• David E. Muller, Franco P. Preparata:
  Restructuring of Arithmetic Expressions For Parallel Evaluation. 534-543
  
• Christos H. Papadimitriou:
  On the complexity of edge traversing. 544-554
  
• Sartaj Sahni, Teofilo F. Gonzalez:
  P-Complete Approximation Problems. 555-565
  
• Andrew Chi-Chih Yao, Foong Frances Yao:
  Lower Bounds on Merging Networks. 566-571
  
• R. A. Cody, Edward G. Coffman Jr.:
  Errata: ``Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices''. 572
  

Volume 23, Number 4, October 1976

• G. E. Peterson:
  Theorem Proving with Lemmas. 573-581
  
• Seymour Ginsburg, Nancy A. Lynch:
  Size complexity in context-free grammars forms. 582-598
  
• Yoram Yakimovsky:
  Boundary and Object Detection in Real World Images. 599-618
  
• Mark J. Eisner, Dennis G. Severance:
  Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases. 619-635
  
• D. E. Heller, D. K. Stevenson, J. F. Traub:
  Accelerated Iterative Methods for the Solution of Tridiagonal Systems on Parallel Computers. 636-654
  
• John L. Bruno:
  Sequencing Jobs with Stochastic Task Structures on a Single Machine. 655-664
  
• Teofilo F. Gonzalez, Sartaj Sahni:
  Open Shop Scheduling to Minimize Finish Time. 665-679
  
• Zvi Rosberg, I. Adiri:
  Multilevel Queues with Extremal Priorities. 680-690
  
• Ben Wegbreit:
  Verifying Program Performance. 691-699
  
• John P. Hayes:
  Enumeration of Fanout-Free Boolean Functions. 700-709
  
• Shimon Even, Robert Endre Tarjan:
  A Combinatorial Problem Which Is Complete in Polynomial Space. 710-719
  
• Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo:
  Space and Time Hierarchies for Classes of Control Structures and Data Structures. 720-732
  
• Maarten H. van Emden, Robert A. Kowalski:
  The Semantics of Predicate Logic as a Programming Language. 733-742