Information Processing Letters, Volume 43

Volume 43, Number 1, 10 August 1992

Sanjeev Saluja: A Note on the Permanent Value Problem. 1-5 BibTeX
Marshall W. Bern, John R. Gilbert: Drawing the Planar Dual. 7-13 BibTeX
Barun Chandra: Does Randomization Help in On-Line Bin Packing? 15-19 BibTeX
Leo Bachmair: Associative-Commutative Reduction Orderings. 21-27 BibTeX
Stefan Schirra: Approximate Decision Algorithms for Approximate Congruence. 29-34 BibTeX
Walter Kern: Learning Convex Bodies under Uniform Distribution. 35-39 BibTeX
Li-Hui Tsai: An Algorithm for Flow Time Minimization and its Asymptotic Makespan Properties. 41-46 BibTeX
Mukesh Singhal, Ajay D. Kshemkalyani: An Efficient Implementation of Vector Clocks. 47-52 BibTeX
Elias Koutsoupias, Christos H. Papadimitriou: On the Greedy Algorithm for Satisfiability. 53-55 BibTeX

Maurizio Martelli, Chiara Tricomi: A New SLDNF-Tree. 57-62 BibTeX
Yeow Meng Chee, Andrew Lim: The Algorithmic Complexity of Colour Switching. 63-68 BibTeX
Fang-Rong Hsu, Richard C. T. Lee, R. C. Chang: Special Subgraphs of Weighted Visibility Graphs. 69-75 BibTeX
Su-Chu Hsu, Shing-Tsaan Huang: A Self-Stabilizing Algorithm for Maximal Matching. 77-81 BibTeX
Tzonelih Hwang: Attacks on Okamoto and Tanaka's One-Way ID-Based Key Distribution System. 81-86 BibTeX
Arunabha Sen, Haiyong Deng, Sumanta Guha: On a Graph Partition Problem with Application to VLSI Layout. 87-94 BibTeX
Mila E. Majster-Cederbaum: Ensuring the Existence of a BCNF-Decomposition that Preserves Functional Dependencies in O(N²) Time. 95-100 BibTeX
Steven Cheung, Francis C. M. Lau: Mesh Permutation Routing with Locality. 101-105 BibTeX
Ming Li, Paul M. B. Vitányi: Optimality of Wait-Free Atomic Multiwriter Variables. 107-112 BibTeX

Oege de Moor: Inductive Data Types for Predicate Transformers. 113-117 BibTeX
Sanjeev Saluja, K. V. Subrahmanyam: On the Power of Enumerative Counting. 119-125 BibTeX
Gerhard J. Woeginger: Finding the Closest Extreme Vertex to a Fixed Point. 127-128 BibTeX
Xiaoquing Liu, Junguk L. Kim: An Effecient Parallel Sorting Algorithm. 129-133 BibTeX
Thomas A. Henzinger: Sooner is Safer Than Later. 135-141 BibTeX
V. I. Galiev, A. F. Polupanov, Igor Shparlinski: Distances from Differences of Roots of Polynomials to the Nearest Integers. 143-146 BibTeX
Wojciech Penczek: On Undecidability of Propositional Temporal Logics on Trace Systems. 147-153 BibTeX
Michele Boreale, Paola Inverardi, Monica Nesi: Complete Sets of Axioms for Finite Basic LOTOS Behavioural Equivalences. 155-160 BibTeX
Vassil S. Dimitrov, Todor Cooklev, B. D. Donevsky: On the Multiplication of Reduced Biquaternions and Applications. 161-164 BibTeX
Do-Hyung Kim, Kwang-Moo Choe: Corrigenda: Yet Another Efficient Backward Execution Algorithm in the AND/OR Process Model. 165 BibTeX , ->IPL 40(4): 201-211 (25 November 1991)
Boleslaw K. Szymanski, Balaram Sinharoy: Corrigenda: Complexity of the Closest Vector Problem in a Lattice Generated by (0, 1)-Matrix. 167 BibTeX , ->Inf. Process. Lett. 42(3): 121-126(1992) BibTeX

Peter Gemmell, Madhu Sudan: Highly Resilient Correctors for Polynomials. 169-174 BibTeX
Jens Palsberg, Michael I. Schwartzbach: Safety Analysis Versus Type Inference for Partial Types. 175-180 BibTeX
Mihail N. Kolountzakis, Kiriakos N. Kutulakos: Fast Computation of the Euclidian Distance Maps for Binary Images. 181-184 BibTeX
Jean-Camille Birget: Intersection and Union of Regular Languages and State Complexity. 185-190 BibTeX
Zhi-Zhong Chen: A Fast and Efficient Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula. 191-193 BibTeX
Tadao Takaoka: A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem. 195-199 BibTeX
Ronald I. Greenberg, F. Miller Maley: Minimum Separation for Single-Layer Channel Routing. 210-205 BibTeX
Lloyd Allison: Lazy Dynamic-Programming Can Be Eager. 207-212 BibTeX
A. Bagchi: On Sorting in the Presence of Erroneous Information. 213-215 BibTeX
Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg: Voronoi Diagrams of Rigidly Moving Sets of Points. 217-223 BibTeX
Katsushi Inoue, Akira Ito, Itsuo Takanami: A Relationship Between Nondeterministic Turing Machines and 1-Inkdot Turing Machines with Small Space. 225-227 BibTeX

Ju Yuan Hsiao, Chuan Yi Tang: An Efficient Algorithm for Finding a Maximum Weight 2-Independent Set on Interval Graphs. 229-235 BibTeX
Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang: An Efficient Algorithm for Finding a Maximum Weight 2-Independent Set on Interval Graphs. 229-235 BibTeX
Eric J. Schwabe: Embedding Meshes of Trees Into deBruijn Graphs. 237-240 BibTeX
Robin W. Dawes: Some Pursuit-Evasion Problems on Grids. 241-247 BibTeX
R. Satyanarayanan, C. R. Muthukrishnan: A Note on Raymond's Tree Based Algorithm for Distributed Mutual Exclusion. 249-255 BibTeX
Zbigniew J. Czech, George Havas, Bohdan S. Majewski: An Optimal Algorithm for Generating Minimal Perfect Hash Functions. 257-264 BibTeX
Andreas S. Pombortsis: Analysis of Hierarchical Bus-Based Multicomputer Architectures. 265-270 BibTeX
Eugene K. Ressler: Random List Permutations in Place. 271-275 BibTeX
André van Vliet: An Improved Lower Bound for On-Line Bin Packing Algorithms. 277-284 BibTeX

Izidor Jerebic, Roman Trobec: Optimal Routing in Toroidal Networks. 285-291 BibTeX
Maw-Shang Chang, Fu-Hsing Wang: Efficient Algorithms for the Maximum Weight Clique and Maximum Weight Independent Set Problems on Permutation Graphs. 293-295 BibTeX
Sheng-Lung Peng, Maw-Shang Chang: A Simple Linear Time Algorithm for the Domatic Partition Problem on Strongly Chordal Graphs. 297-300 BibTeX
David Scholefield, Hussein S. M. Zedan: Weakest Precondition Semantics for Time and Concurrency. 301-308 BibTeX
Eliezer A. Albacea: A Parallel Algorithm for Edge-Coloring of Graphs with Edge-Disjoint Cycles. 309-314 BibTeX
Cheeha Kim, Jong-Sung Kim: A Mean Value Analysis of the Ethernet Throughput. 315-320 BibTeX
Jie Wang: A Note on Two-Way Probabilistic Automata. 321-326 BibTeX
Hanxiong Chen, Xu Yu, Kazunori Yamaguchi, Hiroyuki Kitagawa, Nobuo Ohbo, Yuzuru Fujiwara: Decomposition - An Approach for Optimizing Queries Including ADT Functions. 327-333 BibTeX
Torben Hagerup: On a Compaction Theorem of Ragde. 335-340 BibTeX