Information Processing Letters, Volume 31

Volume 31, Number 1, April 1989

• Vadim E. Kotov: Andrei P. Ershov (1931-1988). 1-2
• David Ginat, Daniel Dominic Sleator, Robert Endre Tarjan: A Tight Amortized Bound for Path Reversal. 3-5
• T. Kamada, S. Kawai: An Algorithm for Drawing General Undirected Graphs. 7-15
• Alok Aggarwal, Dina Kravets: A Linear Time Algorithm for Finding all Farthest Neighbors in a Convex Polygon. 17-20
• Yves Robert, Bernard Tourancheau, G. Villard: Data Allocation Strategies for the Gauss and Jordan Algorithms on a Ring of Processors. 21-29
• Richard I. Hartley: Drawing Polygons Given Angle Sequences. 31-33
• Vijay Kumar: Concurrency Control on Extendible Hashing. 35-41
• Stephan Olariu, J. Randall: Welsh-Powell Opposition Graphs. 43-46
• S. Yu: A Pumping Lemma for Deterministic Context-Free Languages. 47-51
• Hubert de Fraysseix, H. Imai: Notes on Oriented Depth-First Search and Longest Paths. 53-56

Volume 31, Number 2, April 1989

• Fabrizio Luccio, Linda Pagli: On the Upper Bound on the Rotation Distance of Binary Trees. 57-60
• Chin-Wen Ho, Richard C. T. Lee: Counting Clique Trees and Computing Perfect Elimination Schemes in Parallel. 61-68
• R. Sundar: Worst-Case Data Structures for the Priority Queue with Attrition. 69-75
• Josep M. Basart, Llorenç Huguet i Rotger: An Approximation Algorithm for the TSP. 77-81
• M. V. Ramakrishna: Analysis of Random Probing Hashing. 83-90
• F. Warren Burton: A Note on Higher-Order Functions Versus Logical Variables. 91-95
• Iain A. Stewart: An Algorithm for Colouring Perfect Planar Graphs. 97-101
• Wojciech Rytter: A Note on Optimal Parallel Transformations of Regular Expressions to Nondeterministic Finite Automata. 103-109

Volume 31, Number 3, May 1989

• David B. Skillicorn, David T. Barnard: Parallel Parsing on the Connection Machine. 111-117
• Satoshi Matsuoka, Tomihisa Kamada, Satoru Kawai: Asymptotic Evaluation of Window Visibility. 119-126
• Gerard Tel, Friedemann Mattern: Comments on ``Ring Based Termination Detection Algorithm for Distributed Computations''. 127-128
• Wei Kuan Shih, Wen-Lian Hsu: An O(n log n+m log log n) Maximum Weight Clique Algorithm for Circular-Arc Graphs. 129-134
• Hans L. Bodlaender: Achromatic Number is NP-Complete for Cographs and Interval Graphs. 135-138
• John N. Tsitsiklis: On the Use of Random Numbers in Asynchronous Simulation via Rollback. 139-144
• Joseph Y.-T. Leung: Bin Packing with Restricted Piece Sizes. 145-149
• Patrick Lentfert, Mark H. Overmars: Data Structures in a Real-Time Environment. 151-155
• Joseph Cheriyan, S. N. Maheshwari: The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network. 157-161
• Martin Beaudry: Characterization of Idempotent Transformation Monoids. 163-166

Volume 31, Number 4, May 1989

• A. Gregori: Unit-Length Embedding of Binary Trees on a Square Grid. 167-173
• X. Wu: Fast Approximations to Discrete Optimal Quantization. 175-179
• Bogdan S. Chlebus: Parallel Iterated Bucket Sort. 181-183
• Vishv M. Malhotra, T. V. To, Kanchana Kanchanasut: An Improved Data-Dependency-Based Backtracking Scheme for Prolog. 185-189
• Sally A. Goldman: A Space Efficient Greedy Triangulation Algorithm. 191-196
• Anujan Varma: Fault-Tolerant Routing in Unique-Path Multistage Interconnection Networks. 197-201
• Friedemann Mattern: An Efficient Distributed Termination Test. 203-208
• Scott D. Carson, Paul Vongsathorn: Error Bounds on Disk Arrangement Using Frequency Information. 209-213
• Dorit S. Hochbaum, Ron Shamir: An O(n log2 n) Algorithm for the Maximum Weighted Tardiness Problem. 215-219

Volume 31, Number 5, June 1989

• Prakash V. Ramanan: Average-Case Analysis of the Smart Next Fit Algorithm. 221-225
• Rafael Casas, Josep Díaz, Jean-Marc Steyaert: Average-Case Analysis of Robinson's Unification Algorithm with Two Different Variables. 227-232
• Manuel E. Bermudez, George Logothetis: Simple Computation of LALR(1) Lookahead Sets. 233-238
• Tom Head: Deciding the Immutability of Regular Codes and Languages Under Finite Transductions. 239-241
• Stephan Olariu: A Simple Linear-Time Algorithm for Computing the RNG and MST of Unimodal Polygons. 243-247
• Samir Khuller: On Computing Graph Closures. 249-255
• Ellen B. Feinberg: Characterizing the Shortest Path of an Object Among Obstacles. 257-264
• Andrew V. Goldberg, Robert Endre Tarjan: A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network. 265-271
• Bernd-Jürgen Falkowski: A Self-Optimizing Prolog Program and the Underlying Statistical Model. 273-276

Volume 31, Number 6, June 1989

• Gunnar Stålmarck: A Note on the Computational Complexity of the Pure Classical Implication Calculus. 277-278
• Hiroshi Nagamochi, Toshihide Ibaraki: On Max-Flow Min-Cut and Integral Flow Properties for Multicommodity Flows in Directed Networks. 279-285
• Dean P. Foster, Rakesh Vohra: Probabilistic Analysis of a Heuristics for the Dual Bin Packing Problem. 287-290
• Serge Yoccoz: Recursive (omega)o-Rule for Proof Systems. 291-294
• Ravi Mukkamala: Some Properties of View-Based Replication Control Algorithms for Distributed Systems. 295-298
• Paola Bertolazzi, Antonio Sassano: A Decomposition Strategy for the Vertex Cover Problem. 299-304
• Ludwik Czaja: Finite Processes in Cause-Effect Structures and Their Composition. 305-310
• Alok Aggarwal, Michael Hawrylycz: On Computing the Closest Boundary Point on the Convex Hull. 311-314
• Svante Carlsson, Jingsen Chen, Thomas Strothotte: A Note on the Construction of Data Structure ``DEAP''. 315-317
• Peter A. Bloniarz, S. S. Ravi: An O(n log n) Lower Bound for Decomposing a Set of Points into Chains. 319-322
• Norbert Eisinger: A Note on the Completeness of Resolution with Self-Resolution. 323-326
• Lloyd Allison: Direct Semantics and Exceptions Define Jumps and Coroutines. 327-330