Information Processing Letters, Volume 48

Volume 48, Number 1, 29 October 1993

Cordelia V. Hall: Using Overloading to Express Distinctions Between Evaluators. 1-8 BibTeX
Adam L. Buchsbaum, Martin C. Carlisle: Determining Uni-Connectivity in Directed Graphs. 9-12 BibTeX
Nabil I. Hachem: An Approximate Analysis of the Performance of Extendible Hashing with Elastic Buckets. 13-20 BibTeX
Mohan Ahuja: Assertions About Past and Future in Highways: Global Flush Broadcast and Flush-Vector-Time. 21-28 BibTeX , Erratum: Inf. Process. Lett. 58(6): 325(1996) BibTeX
Daniel M. Yellin, Charanjit S. Jutla: Finding Extremal Sets in Less than Quadratic Time. 29-34 BibTeX
Tzonelih Hwang: Scheme for Secure Digital Mobile Communications Based on Symmetric Key Cryptography. 35-37 BibTeX
Jorge Santos, Javier Orozco: Rate Monotonic Scheduling in Hard Real-Time Systems. 39-45 BibTeX
Ming-Shing Yu, Cheng-Hsing Yang: A Simple Optimal Parallel Algorithm for the Minimum Coloring Problem on Interval Graphs. 47-51 BibTeX

Howard J. Karloff: Fast Algorithms for Approximately Counting Mismatches. 53-60 BibTeX
Daniele Pretolani: A Linear Time Algorithm for Unique Horn Satisfiability. 61-66 BibTeX
Wuu Yang: An Incremental LL(1) Parsing Algorithm. 67-72 BibTeX
M. D. Atkinson, Louise Walker: Enumerating k-Way Trees. 73-75 BibTeX
Mike A. Steel, Tandy Warnow: Kaikoura Tree Theorems: Computing the Maximum Agreement Subtree. 77-82 BibTeX
Stefan Gärtner: A Remark on the Regulation of k1ET0L Systems. 83-85 BibTeX
Donald D. Chinn, Rakesh K. Sinha: Bounds on Sample Space Size for Matrix Product Verification. 87-91 BibTeX
Sanjay Gupta: On Bounded-Probability Operators and C=P. 93-98 BibTeX
Stefan Voß: Worst-Case Performance of Some Heuristics for Steiner's Problem in Directed Graphs. 99-105 BibTeX

Yeonghwan Tscha, Yanghee Choi, Kyoon Ha Lee: Rearrangeable Nonblocking Condition for Multi-log_2 N Multiconnection Networks. 107-112 BibTeX
Nimish R. Shah: A Parallel Algorithm for Constructing Projection Polyhedra. 113-119 BibTeX
Ee-Chien Chang, Weiguo Wang, Mohan S. Kankanhalli: Multidimensional On-Line Bin-Packing: An Algorithm and its Average-Case Analysis. 121-125 BibTeX
Satoshi Fujita, Masafumi Yamashita: Fast Gossiping on Square Mesh Computers. 127-130 BibTeX
Debra A. Hensgen, David L. Sims, David Charley: A Fair Banker's Algorithm for Read and Write Locks. 131-137 BibTeX
Detlef Sieling, Ingo Wegener: Reduction of OBDDs in Linear Time. 139-144 BibTeX
K. V. S. Ramarao, S. Venkatesan: The Lower Bounds on Distributed Shortest Paths. 145-149 BibTeX
Hachemi Bennaceur, Gérard Plateau: An Exact Algorithm for the Constraint Satisfaction Problem: Application to Logical Inference. 151-158 BibTeX

C. M. Khoong: Optimal Parallel Construction of Heaps. 159-161 BibTeX
DongGill Lee, Kwang-Moo Choe, Taisook Han: A Description of Dynamic Behavior for Compilers Based on Object Oriented Modeling. 163-170 BibTeX
Georg Reichwein, José Luiz Fiadeiro: Models for the Substitution Axiom of UNITY Logic. 171-176 BibTeX
Ying Teh Tsai, Chuan Yi Tang: The Competitiveness of Randomized Algorithms for On-Line Steiner Tree and On-Line Spanning Tree Problems. 177-182 BibTeX
Zoltán Fülöp, Pál Gyenizse: On Injectivity of Deterministic Top-Down Tree Transducers. 183-188 BibTeX
Kian-Lee Tan, Hongjun Lu: On Resource Scheduling of Multi-Join Queries in Parallel Database Systems. 189-195 BibTeX
Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: A Short Proof of the Dilation of a Toroidal Mesh in a Path. 197-199 BibTeX
Harry Buhrman, Leen Torenvliet, Peter van Emde Boas: Twenty Questions to a P-Selector. 201-204 BibTeX
Maw-Shang Chang, Yi-Chang Liu: Polynomial Algorithms for the Weighted Perfect Domination Problems on Chordal Graphs and Split Graphs. 205-210 BibTeX

Kazuo Iwano, Naoki Katoh: Efficient Algorithms for Finding the Most Vital Edge of a Minimum Spanning Tree. 211-213 BibTeX
Theodore Johnson, Krishna Harathi: A Simple Correctness Proof of the MCS Contention-Free Lock. 215-220 BibTeX
Dana L. Grinstead, Peter J. Slater, Naveed A. Sherwani, Nancy D. Holmes: Efficient Edge Domination Problems in Graphs. 221-228 BibTeX
Lydia E. Kavraki, Jean-Claude Latombe, Randall H. Wilson: On the Complexity of Assembly Partitioning. 229-235 BibTeX
Jang-Ping Sheu, Wen-Hwa Liaw, Tzung-Shi Chen: A Broadcasting Algorithm in Star Graph Interconnection Networks. 237-241 BibTeX
Yordan Rouskov, Pradip K. Srimani: Fault Diameter of Star Graphs. 243-251 BibTeX
Mordecai J. Golin, Robert Sedgewick: Queue-Mergesort. 253-259 BibTeX
Alain Billionnet: Partitioning Multiple-Chain-Like Task Across a Host-Satellite System. 261-266 BibTeX

Karel Culik II, Jarkko Kari: Parametrized Recurrent Systems for Image Generation. 267-274 BibTeX
Marion Rodrigues, Hasan Ural: Exact Solutions for the Construction of Optimal Length Test Sequences. 275-280 BibTeX
Millist W. Vincent, Bala Srinivasan: A Note on Relation Schemes which are in 3NF but not in BCNF. 281-283 BibTeX
Katsushi Inoue, Akira Ito, Itsuo Takanami, Tsunehiro Yoshinaga: A Note on Multi-Inkdot Nondeterministic Turing Machines with Small Space. 285-288 BibTeX
Krishnan Pillaipakkamnatt, Vijay V. Raghavan: A Linear Time Equivalene Test for Read-Twice DNF Formulas. 289-295 BibTeX
Pierre Fraigniaud, Claire Kenyon, Andrzej Pelc: Finding a Target Subnetwork in Sparse Networks with Random Faults. 297-303 BibTeX
Olivier Goldschmidt, Dorit S. Hochbaum, Gang Yu: A Modified Greedy Heuristic for the Set Covering Problem with Improved Worst Case Bound. 305-310 BibTeX
Peter Dankelmann: Computing the Average Distance of an Interval Graph. 311-314 BibTeX
Kevin I.-J. Ho, Joseph Y.-T. Leung, W.-D. Wei: Complexity of Scheduling Tasks with Time-Dependent Execution Times. 315-320 BibTeX