Information Processing Letters, Volume 44

Volume 44, Number 1, 9 November 1992

Soon Myoung Chung:
Indexed Extendible Hashing. 1-6
Shigeru Masuyama, Shozo Naito:
Deciding Whether Graph G has Page Number One is in NC. 7-10
Vangelis Th. Paschos:
A (Delta/2)-Approximation Algorithm for the Maximum Independent Set Problem. 11-13
Ming-Shing Yu, Cheng-Hsing Yang:
An Optimal Parallel Algorithm for the Domatic Partition Problem on an Interval Graph Given its Sorted Model. 15-22
Peter L. Hammer, Alexander Kogan:
Horn Functions and Their DNFs. 23-29
Tzonelih Hwang:
Efficient ID-Based Key Distribution with Tamperfree Devices. 31-34
Shyam Kapur, Gianfranco Bilardi:
On Uniform Learnability of Language Families. 35-38
Vijay K. Garg:
Some Optimal Algorithms for Decomposed Partially Ordered Sets. 39-43
N. Ch. Veeraraghavulu, P. Sreenivasa Kumar, C. E. Veni Madhavan:
A Linear-Time Algorithm for Isomorphism of a Subclass of Chordal Graphs. 45-49
Ahmad Sharary, Nejib Zaguia:
On a Setup Optimization Problem for Interval Orders. 51-55

Mireille Bousquet-Mélou:
The Number of Minimal Word Chains Computing the Thue-Morse Word. 57-64
Paul Gastin, Edward Ochmanski, Antoine Petit, Brigitte Rozoy:
Decidability of the Star Problem in A* x {b}*. 65-71
Bettina De Iaco, Fabrizio Luccio:
Finding all the Palindromes in a Binary Tree in Linear Time and Space. 73-77
Ming-Yang Kao, Fang Wan:
Not all Planar Digraphs have Small Cycle Separators. 79-83
Masakatu Morii, Masao Kasahara:
Perfect Staircase Profile of Linear Complexity for Finite Sequences. 85-89
Rong-Jaye Chen, Yu-Song Hou:
Non-Associative Parallel Prefix Computation. 91-94
Krishnendu Mukhopadhyaya, Bhabani P. Sinha:
Hamiltonian Graphs with Minimum Number of Edges for Fault-Tolerant Topologies. 95-99
Kim-Heng Teo, Tai-Ching Tuan:
An Efficient One-Side Height Minimization Algorithm for Routing Around a Rectangle. 101-105
Been-Chian Chien, Wei-Pang Yang:
The Worst Case Analysis of Algorithm on Multiple Stacks Manipulation. 107-111

Marco Cadoli:
The Complexity of Model Checking for Circumscriptive Formulae. 113-118
Daniel P. Bovet, Stefano Varricchio:
On the Regularity of Languages on a Binary Alphabet Generated by Copying Systems. 119-123
Erkki Mäkinen:
Remarks on the Structural Grammatical Inference Problem for Context-Free Grammars. 125-127
Jorge Lobo, V. S. Subrahmanian:
Relating Minimal Models and Pre-Requisite-Free Normal Defaults. 129-133
James J. Lu, Lawrence J. Henschen:
The Completeness of GP-Resolution for Annotated Logics. 135-140
Yijie Han, Bhagirath Narahari, Hyeong-Ah Choi:
Mapping a Chain Task to Chained Processors. 141-148
Victor Y. Pan, Akimou Sadikou, Elliott Landowne:
Polynomial Division with a Remainder by Means of Evaluation and Interpolation. 149-153
Subir Kumar Ghosh, Anil Maheshwari:
An Optimal Parallel Algorithm for Computing Furthest Neighbors in a Tree. 155-160
Gerhard J. Woeginger:
The Complexity of Finding Arborescences in Hypergraphs. 161-164
John Bainbridge:
A Heuristic Method for Generating Large Random Expressions. 165-170
Jan K. Pachl:
Corrigendum: A Simple Proof of a Completeness Result for Leads-To in the UNITY Logic. 171, (see: Inf. Process. Lett. 41(1): 35-38 (1992))

Mukesh Dalal, David W. Etherington:
A Hierarchy of Tractable Satisfiability Problems. 173-180
Louxin Zhang:
The Pre-NTS Property is Undecidable for Context-Free Grammars. 181-184
Ke Wang, Li-Yan Yuan:
Preservation of Integrity Constraints in Definite DATALOG Programs. 185-193
Tao Jiang, Ming Li, Ding-Zhu Du:
A Note on Shortest Superstrings with Flipping. 195-199
Hsun-Wen Chang, Kuo-Liang Chung:
Fault-Tolerant Routing in Unique-Path Multistage Omega Network. 201-204
Sanjay Gupta:
On the Closure of Certain Function Classes Under Integer Division by Polynomially-Bounded Functions. 205-210
Akihisa Tamura, Yoshiko Tamura:
Degree Constrained Tree Embedding Into Points in the Plane. 211-214
Rafael Dueire Lins:
Cyclic Reference Counting with Lazy Mark-Scan. 215-220
Silvano Martello, Paolo Toth:
A Note on 0.5-Bounded Greedy Algorithms for the 0/1 Knapsack Problem. 221-222
Alexander A. Shvartsman:
An Efficient Write-All Algorithm for Fail-Stop PRAM Without Initialized Memory. 223-231

Amihood Amir, Martin Farach:
Two-Dimensional Dictionary Matching. 233-239
Jer-Shyan Wu, Rong-Jaye Chen:
The Towers of Hanoi Problem with Parallel Moves. 241-243
Jyh-Han Lin, Jeffrey Scott Vitter:
Approximation Algorithms for Geometric Median Problems. 245-249
Amotz Bar-Noy, Rajeev Motwani, Joseph Naor:
The Greedy Algorithm is Optimal for On-Line Edge Coloring. 251-253
Fabrizio d'Amore, Paolo Giulio Franciosa:
On the Optimal Binary Plane Partition for Sets of Isothetic Rectangles. 255-259
Mark H. Overmars:
Point Location in Fat Subdivisions. 261-265
Peter Rossmanith, Wojciech Rytter:
Oberservation on log(n) Time Parallel Recognition of Unambiguous cfl's. 267-272
Gopal Gupta:
Dynamic Parallel Evaluation of the Cross-Product Set Using Time-Stamps. 273-280
Ronald I. Greenberg, Joseph JáJá, Sridhar Krishnamurthy:
On the Difficulty of Manhattan Channel Routing. 281-284
Eliezer Dekel, Jie Hu, Wen Ouyang:
An Optimal Algorithm for Finding Compact Sets. 285-289

Joost Engelfriet:
An Elementary Proof of Double Greibach Normal Form. 291-293
Uriel Feige:
On the Complexity of Finite Random Functions. 295-296
Sundar Vishwanathan:
An Approximation Algorithm for the Asymmetric Travelling Salesman Problem with Distances One and Two. 297-302
Lance Fortnow, Mario Szegedy:
On the Power of Two-Local Random Reductions. 303-306
David A. Cohen, Elizabeth A. Scott:
Rationality of Division Orderings. 307-311
Adriano Pascoletti:
An Optimal Algorithm for the Period of a Strongly Connected Digraph. 313-316
Arup Acharya, B. R. Badrinath:
Recording Distributed Snapshots Based on Causal Order of Message Delivery. 317-321
Arup Acharya, B. R. Badrinath: Recording Distributed Snapshots Based on Causal Order of Message Delivery. 317-321
Shai Simonson, Ivan Hal Sudborough:
On the Complexity of Tree Embedding Problems. 323-328
Hing Leung:
A Note on Finitely Ambiguous Distance Automata. 329-331
Gang Luo, Gregor von Bochmann, Anindya Das, Cheng Wu:
Failure-Equivalent Transformation of Transition Systems to Avoid Internal Actions. 333-343
Dany Breslauer:
An On-Line String Superprimitivity Test. 345-347

Last update Sat May 18 20:36:41 2013 CET by the DBLP Team —

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