Information Processing Letters, Volume 43

Volume 43, Number 1, 10 August 1992

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

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

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

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

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

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

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

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