Information Processing Letters, Volume 38

Volume 38, Number 1, 12 April 1991

Victor J. Dielissen, Anne Kaldewaij: Rectangular Partition is Polynomial in Two Dimensions but NP-Complete in Three. 1-6
Pavel Goralcik, A. Goralciková, Václav Koubek: Alternation with a Pebble. 7-13
Ivan Stojmenovic: Bisections and Ham-Sandwich Cuts of Convex Polygons and Polyhedra. 15-21
Ahmed K. Elmagarmid, Weimin Du: Integrity Aspects of Quasi Serializability. 23-28
Shi-Jinn Horng, Wen-Tsuen Chen, Ming-Yi Fang: Optimal Speed-Up Algorithms for Template Matching on SIMD Hypercube Multiprocessors with Restricted Local Memory. 29-37
Victor Shoup: Smoothness and Factoring Polynomials Over Finite Fields. 39-42
Xu Cheng: A Graph Transformation Algorithm for Concurrency Control in a Partitioned Database. 43-48
Calvin Ching-Yuen Chen, Sajal K. Das, Selim G. Akl: A Unified Approach to Parallel Depth-First Traversals of General Trees. 49-55

Maxime Crochemore, Wojciech Rytter: Efficient Parallel Algorithms to Test Square-Freeness and Factorize Strings. 57-60
Carme Àlvarez, Joaquim Gabarró: The Parallel Complexity of Two Problems on Concurrency. 61-70
Hsu-Chun Yen: A Polynomial Time Algorithm to Decide Pairwise Concurrency of Transitions for 1-Bounded Conflict-Free Petri Nets. 71-76
Giovanni Manzini: Radix Sort on the Hypercube. 77-81
Joao Meidanis: Lower Bounds for Arithmetic Problems. 83-87
Xavier Messeguer: Dynamic Behaviour in Updating Process Over BST of Size Two with Probabilistic Deletion Algorithms. 89-100
Jayadev Misra: Phase Synchronization. 101-105
Steven Minsker: The Towers of Antwerpen Problem. 107-111

Ming-Yang Kao, Stephen R. Tate: Online Matching with Blocked Input. 113-116
David Fernández-Baca, Mark A. Williams: On Matroids and Hierarchical Graphs. 117-121
Günter Rote: Computing the Minimum Hausdorff Distance Between Two Point Sets on a Line Under Translation. 123-127
Lars Langemyr: Circuits for Computing the GCD of Two Polynomials Over an Algebraic Number Field. 129-134
Charles U. Martel: Self-Adjusting Multi-Way Search Trees. 135-141
Subbiah Rajanarayanan, S. Sitharama Iyengar: A New Optimal Distributed Algorithm for the Set Intersection Problem. 143-148
Günter Rote, Gerhard J. Woeginger, Binhai Zhu, Zhengyan Wang: Counting k-Subsets and Convex k-gons in the Plane. 149-151
Michal Mnuk: A div(n) Depth Bollean Circuit for Smooth Modular Inverse. 153-156
P. Pramanik, P. K. Das, A. K. Bandyopadhyay, D. Q. M. Fay: A Deadlock-Free Communication Kernel for Loop Architecture. 157-161
Dragan M. Acketa, Jovisa D. Zunic: On the Number of Linear Partitions of the (m, n)-Grid. 163-168

James H. Bradford, T. A. Jenkyns: On the Inadequacy of Tournament Algorithms for the N-SCS Problem. 169-171
Marek Chrobak, Lawrence L. Larmore: A Note on the Server Problem and a Benevolent Adversary. 173-175
Rolf Floren: A Note on ``A Faster Approximation Algorithm for the Steiner Problem in Graphs''. 177-178
Andrew V. Goldberg: Processor-Efficient Implementation of a Maximum Flow Algorithm. 179-185
Laurent Siklóssy, Eduard Tulp: The Space Reduction Method: A Method to Reduce the Size of Search Spaces. 187-192
William I. Gasarch: On Selecting the k Largest with Restricted Quadratic Queries. 193-195
Ernst L. Leiss, Hari N. Reddy: Embedding Complete Binary Trees Into Hypercubes. 197-199
Ron Shonkwiler: Computing the Hausdorff Set Distance in Linear Time for Any L_p Point Distance. 201-207
Josep M. Basart: Some Upper Bounds for Minimal Trees. 209-213
Jin-yi Cai, Lane A. Hemachandra: A Note on Enumarative Counting. 215-219
Markku Sakkinen: Selftype is a Special Case. 221-224

Wojciech Rytter, Ahmed Saoudi: On the Complexity of the Recognition of Parallel 2D-Image Languages. 225-229
John Hershberger: A New Data Structure for Shortest Path Queries in a Simple Polygon. 231-235
Andrzej Lingas: Bit Complexity of Matrix Products. 237-242
Myoung-Ho Kim, Sakti Pramanik: The FX Distribution Method for Parallel Processing of Partial Match Queries. 243-252
Gerhard J. Woeginger: On Minimizing the Sum of k Tardinesses. 253-256
Susanne E. Hambrusch, Michael Luby: Parallel Asynchronous Connected Components in a Mesh. 257-263
T. Z. Kalamboukis, S. L. Mantzaris: Towards Optimal Distributed Election on Chordal Rings. 265-270
Farshad Fotouhi, Sakti Pramanik: Problem of Optimizing the Number of Block Accesses in Performing Relational Join is NP-Hard. 271-275
Jirí Matousek: Computing Dominances in E^n. 277-278
Timothy Law Snyder: Corrigendum: Lower Bounds for Rectilinear Steiner Trees. 279 , ->Inf. Process. Lett. 37(2): 71-74(1991)
Myung-Joon Lee, Kwang-Moo Choe: Corrigenda: SLR(k) Covering for LR(k) Grammars. 281 , ->Inf. Process. Lett. 37(6): 337-347(1991)

Peter B. Danzig: A Cooperative Game with Applications to Computer Networks. 283-289
Franco P. Preparata: Inverting a Vandermonde Matrix in Minimum Parallel Time. 291-294
Robert Kennedy: Parallel Cardinality Stacks and an Application. 295-299
Sandy Irani: Two Results on the List Update Problem. 301-306
Kenneth Luo, William Klostermeyer, Yuan-Chieh Chow, Richard E. Newman-Wolfe: Optimal Deadlock Resolutions in Edge-Disjoint Reducible Wait-For Graphs. 307-313
Shahram Latifi: Distributed Subcube Identification Algorithms for Reliable Hypercupes. 315-321
Jerzy R. Nawrocki: Conflict Detection and Resolution in a Lexical Analyzer Generator. 323-328
Kieran T. Herley: A Note on the Token Distribution Problem. 329-334
David Zuckerman: On the Time to Traverse all Edges of a Graph. 335-337
Dejan Zivkovic: A Fast Algorithm for Finding the Compact Sets. 339-342