Information Processing Letters, Volume 62

Volume 62, Number 1, 14 April 1997

• Vesa Halava, Tero Harju, Lucian Ilie:
  On a Geometric Problem of Zigzags. 1-4
  
• Burghard von Karger, Rudolf Berghammer:
  Computing Kernels in Directed Bichromatic Graphs. 5-11
  
• Anna Gál:
  A Simple Function that Requires Exponential Size Read-Once Branching Programs. 13-16
  
• H. V. Jagadish:
  Analysis of the Hilbert Curve for Representing Two-Dimensional Space. 17-22
  
• Manolis Gergatsoulis:
  Unfold/fold Transformations for Disjunctive Logic Programs. 23-29
  
• Ekkart Kindler, Rolf Walter:
  Mutex Needs Fairness. 31-39
  
• Ariel Orda, Michael Merritt:
  Efficient Test & Set Constructions for Faulty Shared Memory. 41-46
  
• Javier Orozco, Ricardo Cayssials, Jorge Santos, Edgardo Ferro:
  802.4 Rate Monotonic Scheduling in Hard Real-Time Environments: Setting the Medium Access Control Parameters. 47-55
  

Volume 62, Number 2, 28 April 1997

• Erkki Mäkinen:
  Inferring Uniquely Terminating Regular Languages from Positive Data. 57-60
  
• Assef Chmeiss, Philippe Jégou:
  A Generalization of Chordal Graphs and the Maximum Clique Problem. 61-66
  
• Hee-Joong Kang, Kawon Kim, Jin H. Kim:
  Approximating Optimally Discrete Probability Distribution with kth-Order Dependency for Combining Multiple Decisions. 67-75
  
• Sung-Ming Yen, Kuo-Hong Liao:
  Shared Authentication Token Secure Against Replay and Weak Key Attacks. 77-80
  
• Goos Kant, Giuseppe Liotta, Roberto Tamassia, Ioannis G. Tollis:
  Area Requirement of Visibility Representations of Trees. 81-88
  
• Kasturi R. Varadarajan, Pankaj K. Agarwal:
  Linear Approximation of Simple Objects. 89-94
  
• Amihood Amir, Emanuel Dar:
  An Improved Deterministic Algorithm for Generating Different Many-Element Random Samples. 95-101
  
• Dany Breslauer, Artur Czumaj, Devdatt P. Dubhashi, Friedhelm Meyer auf der Heide:
  Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine. 103-110
  

Volume 62, Number 3, 14 May 1997

• Fabrice Bouquet, Philippe Jégou:
  Using OBDDs to Handle Dynamic Constraints. 111-120
  
• David Eppstein:
  Dynamic Connectivity in Digital Images. 121-126
  
• Robert Glück, Andrei V. Klimov:
  A Regeneration Scheme for Generating Extensions. 127-134
  
• Sarmad Abbasi, Anirvan Sengupta:
  An O(n log n) Algorithm for Finding Dissimilar Strings. 135-139
  
• Ching-Nung Yang, Chi-Sung Laih:
  A Note on Error-Correcting Codes for Authentication and Subliminal Channels. 141-143
  
• Eric Bach:
  The Complexity of Number-Theoretic Constants. 145-152
  
• Valerie King, Chung Keung Poon, Vijaya Ramachandran, Santanu Sinha:
  An Optimal EREW PRAM Algorithm for Minimum Spanning Tree Verification. 153-159
  
• Andreas Döring, Wolfgang J. Paul:
  Decimal Adjustment of Long Numbers in Constant Time. 161-163
  
• Marius Zimand:
  Large Sets in AC⁰ have Many Strings with Low Kolmogorov Complexity. 165-170
  

Volume 62, Number 4, 28 May 1997

• Gabriel Istrate:
  The Strong Equivalence of ET0L Grammars. 171-176
  
• Rimli Sengupta:
  Cancellation is Exponentially Powerful for Computing the Determinant. 177-181
  
• Wan Fokkink:
  Unification for Infinite Sets of Equations Between Finite Terms. 183-188
  
• Shoichi Hirose, Katsuo Ikeda:
  A Conference Key Distribution System for the Star Configuration Based on the Discrete Logarithm Problem. 189-192
  
• Guozhu Dong, Chaoyi Pang:
  Maintaining Transitive Closure in First Order After Node-Set and Edge-Set Deletions. 193-199
  
• Qian-Ping Gu, Shietung Peng:
  Node-To-Set Disjoint Paths Problem in Star Graphs. 201-207
  
• Felipe Cucker, Pascal Koiran, Martín Matamala:
  Complexity and Dimension. 209-212
  
• Feng Bao, Aohan Mei, Yoshihide Igarashi:
  Average Competitive Ratios of On-Line Spanning Trees. 213-216
  
• Wim F. J. Verhaegh, Emile H. L. Aarts:
  A Polynomial-Time Algorithm for Knapsack with Divisible Item Sizes. 217-221
  

Volume 62, Number 5, 13 June 1997

• Md. Mozammel Huq Azad Khan, Md. Shamsul Alam:
  Algorithms for Conversion of Minterms to Positive Polarity Reed-Muller Coefficients and Vice Versa. 223-230
  
• Rabah Harbane, Carles Padró:
  Spanners of de Bruijn and Kautz Graphs. 231-236
  
• Rabah Harbane, Carles Padró:
  Spanners of Underlying Graphs of Iterated Line Digraphs. 245-250
  
• Timothy Lambert:
  An Optimal Algorithm for Realizing a Delaunay Triangulation. 245-250
• James W. Gray III:
  On the Clark-Jacob Version of SPLICE/AS. 251-254
  
• Wai Yin Mok:
  On Keys and Normal Forms. 255-258
  
• Montserrat Hermo:
  Compressibility and Uniform Complexity. 259-264
  
• V. A. Vassiliev:
  On Decision Trees for Orthants. 265-268
  
• Anna Formica, Michele Missikoff:
  A Verification Algorithm for Inheritance Hierarchies in Object-Oriented Databases. 269-279
  

Volume 62, Number 6, 27 June 1997

• Jean-Luc Fouquet, Igor Parfenoff, Henri Thuillier:
  An O(n) Time Algorithm for Maximum Matching in P₄-Tidy Graphs. 281-287
  
• Jacques Justin, Giuseppe Pirillo:
  On Some Factorizations of Infinite Words by Elements of Codes. 289-294
  
• Ravi Kumar, Rina Panigrahy, Alexander Russell, Ravi Sundaram:
  A Note on Optical Routing on Trees. 295-300
  
• Yuan Ma, Serge A. Plotkin:
  An Improved Lower Bound for Load Balancing of Tasks with Unknown Duration. 301-303
  
• Masataka Sassa, Takuya Ookubo:
  Systematic Debugging Method for Attribute Grammar Description. 305-313
  
• Shin-Ichi Nakano, Md. Saidur Rahman, Takao Nishizeki:
  A Linear-Time Algorithm for Four-Partitioning Four-Connected Planar Graphs. 315-322
  
• Shin-ichi Nakayama, Shigeru Masuyama:
  A Parallel Algorithm for Solving the Coloring Problem on Trapezoid Graphs. 323-327
  
• Paul Pritchard:
  An Old Sub-Quadratic Algorithm for Finding Extremal Sets. 329-334