Information Processing Letters, Volume 63

Volume 63, Number 1, 14 July 1997

Richard S. Bird, Jesús N. Ravelo:
On Computing Representatives. 1-7
Enrico Nardelli, Vincenzo Mastrobuoni, Alesiano Santomo:
On building the Transitive Reduction of a Two-Dimensional Poset. 9-12
Hon-Chan Chen, Yue-Li Wang:
A Linear Time Algorithm for Finding Depth-First Spanning Trees on Trapezoid Graphs. 13-18
Chin-Chen Chang, Shin-Jia Hwang:
A Simple Approach for Generating RSA Keys. 19-21
Paola Flocchini, Bernard Mans, Nicola Santoro:
On the Impact of Sense of Direction on Message Complexity. 23-31
Eric T. Bax, Joel Franklin:
A Permanent Formula with Many Zero-Valued Terms. 33-39
Marten van Dijk:
More Information Theoretical Inequalities to be Used in Secret Sharing? 41-44
Zoran Ivkovic, Errol L. Lloyd:
Partially Dynamic bin Packing can be Solved Within 1 + \varepsilon in (Amortized) Polylogarithmic Time. 45-50
Jiri Sgall:
A Lower Bound for Randomized On-Line Multiprocessor Scheduling. 51-55

Kuo-Liang Chung:
A Fast Algorithm for Stereo Matching. 57-61
Refael Hassin, Shlomi Rubinstein:
An Approximation Algorithm for Maximum Packing of 3-Edge Paths. 63-67
J. G. Gaines:
Partitions with Minimum Entropy of Regions in R². 69-73
Gudmund Skovbjerg Frandsen, Sven Skyum:
Dynamic Maintenance of Majority Information in Constant Time per Update. 75-78
Marek Chrobak, Lawrence L. Larmore, Carsten Lund, Nick Reingold:
A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem. 79-83
Costas Busch, Marios Mavronicolas:
Impossibility Results for Weak Threshold Networks. 85-90
Wilfried Imrich, Sandi Klavzar:
Recognizing Hamming Graphs in Linear Time and space. 91-95
Tiziana Calamoneri, Andrea Sterbini:
3D Straight-Line Grid Drawing of 4-Colorable Graphs. 97-102
Jan-Ming Ho, Ming-Tat Ko:
Bounded Fan-Out m-Center Problem. 103-108
Yehuda Afek, Menashe Cohen, Eyal Haalman:
The Bit Complexity of the Predecessor Problem. 109-112
Robert Geist:
Performance Bounds for Modeling NUMA Architectures. 113-117

Abdel Krim Amoura:
A Note on Scheduling Multiprocessor Tasks with Precedence Constraints on Parallel Processors. 119-122
Shou-Hsuan Stephen Huang, Hongfei Liu, Rakesh M. Verma:
On Embedding Rectangular Meshes into Rectangular Meshes of Smaller Aspect Ratio. 123-129
Oded Goldreich, Dana Ron:
On Universal Learning Algorithms. 131-136
Christian Schittenkopf, Gustavo Deco, Wilfried Brauer:
Finit Automata-Models for the Investigation of Dynamical Systems. 137-141
Peter Jonsson:
A Nonapproximability Result for Finite Function Generation. 143-145
A. A. Arratia-Quesada, Iain A. Stewart:
Generalized Hex and Logical Characterizations of Polynomial Space. 147-152
Bernd Borchert, Riccardo Silvestri:
A Characterization of the Leaf Language Classes. 153-158
Loe M. G. Feijs, Rob C. van Ommering:
Abstract Derivation of Transitive Closure Algorithms. 159-164
Ludek Kucera:
Computing OR on a Randomized Fixed Adversary CRCW PRAM. 165-166
Dieter Kratsch, Lorna Stewart:
Total Domination and Transformation. 167-170

János Csirik, Gerhard J. Woeginger:
Shelf Algorithms for On-Line Strip Packing. 171-175
Kumar N. Lalgudi, Marios C. Papaefthymiou:
Computing Strictly-Second Shortest Paths. 177-181
Kunsoo Park, Sang Lyul Min, Yookun Cho:
The Working Set Algorithm has Competitive Ratio Less Than Two. 183-188
Prabhudev Konana, Juhnyoung Lee, Sudha Ram:
Updating Timestamp Interval for Dynamic Adjustment of Serialization Order in Optimistic Concurrency Control-Time Interval (OCCTI) Protocol. 189-193
Maxime Crochemore, Thierry Lecroq:
Tight Bounds on the Complexity of the Apostolico-Giancarlo Algorithm. 195-203
Sying-Jyan Wang:
Distributed Routing in a Fault-Tolerant Multistage Interconnection Network. 205-210
Nader H. Bshouty, Yishay Mansour, Baruch Schieber, Prasoon Tiwari:
A Tight Bound for Approximating the Square Root. 211-213
Mark de Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf:
Computing a Single Cell in the Overlay of Two Simple Polygons. 215-219
Jürgen Ebert, Gottfried Vossen:
I-Serializability: Generalized Correctness for Transaction-Based Environments. 221-227

S. Louis Hakimi, Edward F. Schmeichel, Neal E. Young:
Orienting Graphs to Optimize Reachability. 229-235
Clark F. Olson:
An Approximation Algorithm for Least Median of Squares Regression. 237-241
Doron Peled, Thomas Wilke:
Stutter-Invariant Temporal Properties are Expressible Without the Next-Time Operator. 243-246
Wei-Bin Lee, Chin-Chen Chang:
Authenticated Encryption Schemes with Linkage Between Message Blocks. 247-250
Helmut Veith:
Languages Represented by Boolean Formulas. 251-256
Ravi B. Boppana:
The Average Sensitivity of Bounded-Depth Circuits. 257-261
Bang Ye Wu, Chuan Yi Tang:
An O(n) Algorithm for Finding an Optimal Position with Relative Distances in an Evolutionary Tree. 263-269
Li-Chiun Wei, Ruay Shiung Chang:
Broadcast Scheduling in Packet Radio Networks by Hopfield Neural networks. 271-276
Ruay Shiung Chang, Shing-Jiuan Leu:
The Minimum Labeling Spanning Trees. 277-282
Vincent D. Blondel, John N. Tsitsiklis:
When is a Pair of Matrices Mortal? 283-286

Mikael Goldmann:
On the Power of a Threshold Gate at the Top. 287-293
Vijay K. Garg, J. Roger Mitchell:
Detecting Conjunctions of Global Predicates. 295-302
Sung Kwon Kim:
Logarithmic Width, Linear Area Upward Drawing of AVL Trees. 303-307
Seung-Hoon Kim, Kyungshik Lim, Cheeha Kim:
Efficient Stream Distribution Algorithm for Heterogeneous Multimedia Multicast with Link Capacity Constraint. 309-315
Carlo Blundo, Alfredo De Santis:
Lower Bounds for Robust Secret Sharing Schemes. 317-321
Ngoc-Minh Lê:
On Non-Smooth Convex Distance Functions. 323-329
Fabrizio Luccio, Linda Pagli:
An Insight on PRAM Computational Bounds. 331-336