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
Electronic Edition (link) BibTeX
Burghard von Karger, Rudolf Berghammer:
Computing Kernels in Directed Bichromatic Graphs. 5-11
Electronic Edition (link) BibTeX
Anna Gál:
A Simple Function that Requires Exponential Size Read-Once Branching Programs. 13-16
Electronic Edition (link) BibTeX
H. V. Jagadish:
Analysis of the Hilbert Curve for Representing Two-Dimensional Space. 17-22
Electronic Edition (link) BibTeX
Manolis Gergatsoulis:
Unfold/fold Transformations for Disjunctive Logic Programs. 23-29
Electronic Edition (link) BibTeX
Ekkart Kindler, Rolf Walter:
Mutex Needs Fairness. 31-39
Electronic Edition (link) BibTeX
Ariel Orda, Michael Merritt:
Efficient Test & Set Constructions for Faulty Shared Memory. 41-46
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

Erkki Mäkinen:
Inferring Uniquely Terminating Regular Languages from Positive Data. 57-60
Electronic Edition (link) BibTeX
Assef Chmeiss, Philippe Jégou:
A Generalization of Chordal Graphs and the Maximum Clique Problem. 61-66
Electronic Edition (link) BibTeX
Hee-Joong Kang, Kawon Kim, Jin H. Kim:
Approximating Optimally Discrete Probability Distribution with kth-Order Dependency for Combining Multiple Decisions. 67-75
Electronic Edition (link) BibTeX
Sung-Ming Yen, Kuo-Hong Liao:
Shared Authentication Token Secure Against Replay and Weak Key Attacks. 77-80
Electronic Edition (link) BibTeX
Goos Kant, Giuseppe Liotta, Roberto Tamassia, Ioannis G. Tollis:
Area Requirement of Visibility Representations of Trees. 81-88
Electronic Edition (link) BibTeX
Kasturi R. Varadarajan, Pankaj K. Agarwal:
Linear Approximation of Simple Objects. 89-94
Electronic Edition (link) BibTeX
Amihood Amir, Emanuel Dar:
An Improved Deterministic Algorithm for Generating Different Many-Element Random Samples. 95-101
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

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

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

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

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