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

Last update Mon Feb 13 04:50:40 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page