Information Processing Letters, Volume 68

Volume 68, Number 1, 15 October 1998

Andrew Turpin, Alistair Moffat:
Comment on ``Efficient Huffman Decoding'' and ``An Efficient Finite-State Machine Implementation of Huffman Decoders''. 1-2
Electronic Edition (link) BibTeX
Alfredo García Olaverri, Pedro Jodrá, Javier Tejel:
An Efficient Algorithm for On-Line Searching of Minima in Monge Path-Decomposable Tridimensional Arrays. 3-9
Electronic Edition (link) BibTeX
Alberto Caprara, Romeo Rizzi:
Improving a Family of Approximation Algorithms to Edge Color Multigraphs. 11-15
Electronic Edition (link) BibTeX
Rajeev Govindan, Michael A. Langston, Xudong Yan:
Approximation the Pathwidth of Outerplanar Graphs. 17-23
Electronic Edition (link) BibTeX
Chan-Su Shin, Sung Yong Shin, Kyung-Yong Chwa:
The Widest k-Dense Corridor Problems. 25-31
Electronic Edition (link) BibTeX
Bernd Gärtner, Sven Schönherr:
Exact Primitives for Smallest Enclosing Ellipses. 33-38
Electronic Edition (link) BibTeX
Chi-Hsiang Yeh, Behrooz Parhami:
VLSI Layouts of Complete Graphs and Star Graphs. 39-45
Electronic Edition (link) BibTeX
Wojciech Fraczak, Marek B. Zaremba:
A Non-SOS Operational Semantics for a Process Algebra. 47-54
Electronic Edition (link) BibTeX

Anne Bottreau, Yves Métivier:
Some Remarks on the Kronecker Product of Graphs. 55-61
Electronic Edition (link) BibTeX
Joost P. Warners:
A Linear-Time Transformation of Linear Inequalities into Conjunctive Normal Form. 63-69
Electronic Edition (link) BibTeX
Desh Ranjan, Enrico Pontelli, Gopal Gupta:
Efficient Algorithms for the Temporal Precedence Problem. 71-81
Electronic Edition (link) BibTeX
Joaquim Gabarró, Xavier Messeguer:
Parallel Dictionaries with Local Rules on AVL and Brother Trees. 79-85
Electronic Edition (link) BibTeX
Colin J. Fidge:
A Limitation of Vector Timestamps for Reconstructing Distributed Computations. 87-91
Electronic Edition (link) BibTeX
Srinivasan Venkatesh:
Pseudo-Average Block Sensitivity Equals Average Sensitivity. 93-95
Electronic Edition (link) BibTeX
Kothuri Venkata Ravi Kanth, Ambuj K. Singh:
Efficient Dynamic Range Searching Using Data Replication. 97-105
Electronic Edition (link) BibTeX

Carles Padró:
Robust Vector Space Secret Sharing Schemes. 107-111
Electronic Edition (link) BibTeX
Vincent Vajnovszki:
On the Loopless Generation of Binary Tree Sequences. 113-117
Electronic Edition (link) BibTeX
Marcin Jurdzinski:
Deciding the Winner in Parity Games is in UP \cap co-Up. 119-124
Electronic Edition (link) BibTeX
Amihood Amir, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein:
Efficient Special Cases of Pattern Matching with Swaps. 125-132
Electronic Edition (link) BibTeX
Francesco M. Malvestuto:
A Complete Axiomatization of Full Acyclic Join Dependencies. 133-139
Electronic Edition (link) BibTeX
Chor Ping Low:
A Polynomial Time Solvable Instance of the Feasible Minimum Cover Problem. 141-146
Electronic Edition (link) BibTeX
Witold Charatonik:
An Undecidable Fragment of the Theory of Set Constraints. 147-151
Electronic Edition (link) BibTeX
Valery Gordon, Wieslaw Kubiak:
Single Machine Scheduling with Release and Due Date Assignment to Minimize the Weighted Number of Late Jobs. 153-159
Electronic Edition (link) BibTeX

Nadia Creignou:
Complexity Versus Stability for Classes of Propositional Formulas. 161-165
Electronic Edition (link) BibTeX
Roberto Posenato, Massimo Santini:
A New Lower Bound on Approximability of the Ground State Problem for Tridimensional Ising Spin Glasses. 167-171
Electronic Edition (link) BibTeX
Wim H. Hesselink:
Invariants for the Construction of a Handshake Register. 173-177
Electronic Edition (link) BibTeX
Ding-Ming Kwai, Behrooz Parhami:
Pruned Three-Dimensional Toroidal Networks. 179-183
Electronic Edition (link) BibTeX
Pedro P. Sanchez, Refik Soyer:
Information Concepts and Pairwise Comparison Matrices. 185-188
Electronic Edition (link) BibTeX
Yishay Mansour, Michal Parnas:
Learning Conjunctions with Noise under Product Distributions. 189-196
Electronic Edition (link) BibTeX
Henri Gilbert, Dipankar Gupta, Andrew M. Odlyzko, Jean-Jacques Quisquater:
Attacks on Shamir's `RSA for Paranoids'. 197-199
Electronic Edition (link) BibTeX
Ton Kloks, Haiko Müller, C. K. Wong:
Vertex Ranking of Asteroidal Triple-Free Graphs. 201-206
Electronic Edition (link) BibTeX
Abhijit Sengupta:
On Ring Embedding in Hypercubes with Faulty Nodes and Links. 207-214
Electronic Edition (link) BibTeX
Yi-Chang Cheng, Erl-Huei Lu, Shaw Woei Wu:
A Modified Version of the Rao-Nam Algebraic-Code Encryption Scheme. 215-217
Electronic Edition (link) BibTeX

A. P. Ustimenko:
Colored Cause-Effect Structures. 219-225
Electronic Edition (link) BibTeX
Yuliang Zheng, Hideki Imai:
How to Construct Efficient Signcryption Schemes on Elliptic Curves. 227-233
Electronic Edition (link) BibTeX
KyungOh Lee, Heon Young Yeom:
A Dynamic Scheduling Algorithm for Large Scale Multimedia Servers. 235-240
Electronic Edition (link) BibTeX
Venkatesan Guruswami, C. Pandu Rangan:
A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds. 241-248
Electronic Edition (link) BibTeX
Peter Jonsson:
Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems. 249-253
Electronic Edition (link) BibTeX
Bette Bultena, Frank Ruskey:
An Eades-McKay Algorithm for Well-Formed Parentheses Strings. 255-259
Electronic Edition (link) BibTeX
Matteo Sereno:
Binary Search with Errors and Variable Cost Queries. 261-270
Electronic Edition (link) BibTeX

Josep Rifà:
A New Algebraic Algorithm to Decode the Ternary Golay Code. 271-274
Electronic Edition (link) BibTeX
Rakesh K. Sinha:
Simulation of PRAMs with Scan Primitives by Unbounded Fan-In Circuits. 275-282
Electronic Edition (link) BibTeX
Jorge Calera-Rubio, Rafael C. Carrasco:
Computing the Relative Entropy Between Regular Tree Languages. 283-289
Electronic Edition (link) BibTeX
Janelle J. Harms:
A Simple Optimal Algorithm for Scheduling Variable-Sized Requests. 291-293
Electronic Edition (link) BibTeX
Wen-Ming Yan, Wendy J. Myrvold, Kuo-Liang Chung:
A Formula for the Number of Spanning Trees of a Multi-Star Related Graph. 295-298
Electronic Edition (link) BibTeX
Andrzej Szepietowski:
Weak and Strong One-Way Space Complexity Classes. 299-302
Electronic Edition (link) BibTeX
Pierre Fraigniaud:
Hierarchical Broadcast Networks. 303-305
Electronic Edition (link) BibTeX
Ulrich Kühn:
Local Calculation of Voronoi Diagrams. 307-312
Electronic Edition (link) BibTeX
Ton Kloks, Dieter Kratsch, Haiko Müller:
Bandwidth of Chain Graphs. 313-315
Electronic Edition (link) BibTeX
Michael J. Collins, Bernard M. E. Moret:
Improved Lower Bounds for the Link Length of Rectilinear Spanning Paths in Grids. 317-319
Electronic Edition (link) BibTeX