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
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
Alberto Caprara, Romeo Rizzi:
Improving a Family of Approximation Algorithms to Edge Color Multigraphs. 11-15
Rajeev Govindan, Michael A. Langston, Xudong Yan:
Approximation the Pathwidth of Outerplanar Graphs. 17-23
Chan-Su Shin, Sung Yong Shin, Kyung-Yong Chwa:
The Widest k-Dense Corridor Problems. 25-31
Bernd Gärtner, Sven Schönherr:
Exact Primitives for Smallest Enclosing Ellipses. 33-38
Chi-Hsiang Yeh, Behrooz Parhami:
VLSI Layouts of Complete Graphs and Star Graphs. 39-45
Wojciech Fraczak, Marek B. Zaremba:
A Non-SOS Operational Semantics for a Process Algebra. 47-54

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

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

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

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

Josep Rifà:
A New Algebraic Algorithm to Decode the Ternary Golay Code. 271-274
Rakesh K. Sinha:
Simulation of PRAMs with Scan Primitives by Unbounded Fan-In Circuits. 275-282
Jorge Calera-Rubio, Rafael C. Carrasco:
Computing the Relative Entropy Between Regular Tree Languages. 283-289
Janelle J. Harms:
A Simple Optimal Algorithm for Scheduling Variable-Sized Requests. 291-293
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
Andrzej Szepietowski:
Weak and Strong One-Way Space Complexity Classes. 299-302
Pierre Fraigniaud:
Hierarchical Broadcast Networks. 303-305
Ulrich Kühn:
Local Calculation of Voronoi Diagrams. 307-312
Ton Kloks, Dieter Kratsch, Haiko Müller:
Bandwidth of Chain Graphs. 313-315
Michael J. Collins, Bernard M. E. Moret:
Improved Lower Bounds for the Link Length of Rectilinear Spanning Paths in Grids. 317-319

Last update Fri May 24 20:29:26 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page