Information Processing Letters, Volume 31

Volume 31, Number 1, April 1989

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

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

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

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

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

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