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

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

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

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

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

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