Information Processing Letters, Volume 49

Volume 49, Number 1, 14 January 1994

• Vittoria Gianuzzi: Distributed Termination Detection in Reducible Communication Graphs. 1-8 BibTeX
• Esko Nuutila, Eljas Soisalon-Soininen: On Finding the Strongly Connected Components in a Directed Graph. 9-14 BibTeX
• Mikael Goldmann, Per Grape, Johan Håstad: On Average Time Hierarchies. 15-20 BibTeX
• Kanchana Kanchanasut: A Shortest-Path Algorithm for Manhattan Graphs. 21-25 BibTeX
• Mounir Belbaraka, Ivan Stojmenovic: On Generating B-Trees with Constant Average Delay and in Lexicographic Order. 27-32 BibTeX
• D. Veljan: Computing Values of a Polynomial with Only few Multiplications. 33-37 BibTeX
• Hing-Fung Ting, Andrew Chi-Chih Yao: A Randomized Algorithm for Finding Maximum with O((log n)²) Polynomial Tests. 39-43 BibTeX
• Chong Jye Rhee, Y. Daniel Liang, Sudarshan K. Dhall, S. Lakshmivarahan: Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs. 45-50 BibTeX
• Haim Kaplan, Ron Shamir: The Domatic Number Problem on Some Perfect Graph Families. 51-56 BibTeX

Volume 49, Number 2, 28 January 1994

• Gurdip Singh: Real-Time Leader Election. 57-61 BibTeX
• Min-Soo Jung, Kwang-Moo Choe, Taisook Han: An Efficient Computation of Right Context for LR-Based Error Repair. 63-71 BibTeX
• Sanjeev Saxena: Two-Coloring Linked Lists is NC^1-Complete for Logarithmic Space. 73-76 BibTeX
• Peter Gemmell, Mor Harchol-Balter: Tight Bounds on Expected Time to Add Correctly and Add Mostly Correctly. 77-83 BibTeX
• Joachim Steinbach: Generating Polynomial Orderings. 85-93 BibTeX
• Harry G. Mairson: Generating Words in a Context-Free Language Uniformly at Random. 95-99 BibTeX
• Jan Willem Klop, Aart Middeldorp, Yoshihito Toyama, Roel C. de Vrijer: Modularity of Confluence: A Simplified Proof. 101-109 BibTeX

Volume 49, Number 3, 11 February 1994

• Amihood Amir, Martin Farach, S. Muthukrishnan: Alphabet Dependence in Parameterized Matching. 111-115 BibTeX
• Sung Kwon Kim: The Range Co-Minima Problem. 117-121 BibTeX
• M. Ladermann, H. Petersen: Notes on Looping Deterministic Two-Way Pushdown Automata. 123-127 BibTeX
• Tze Fen Li, Sung Wu Chang: An Algorithm to Estimate the Fraction Defective and The Exponential Mean Life Using Unlabeled Samples. 129-133 BibTeX
• Yukio Shibata, Miyuki Shirahata, Shingo Osawa: Counting Closed Walks in Generalized de Bruijn Graphs. 135-138 BibTeX
• B. S. Panda, S. P. Mohanty: Recognition Algorithm for Intersection Graphs of Edge Disjoint Paths in a Tree. 139-143 BibTeX
• Zoran Jovanovic, Jelena V. Misic: Fault Tolerance of the Star Graph Interconnection Network. 145-150 BibTeX
• Maria Luisa Bonet, Samuel R. Buss: Size-Depth Tradeoffs for Boolean Fomulae. 151-155 BibTeX
• S. B. Yang, Sudarshan K. Dhall, S. Lakshmivarahan: A Processor Efficient MIS Algorithm on Random Graphs. 157-163 BibTeX

Volume 49, Number 4, 25 February 1994

• Chien-Min Wang: A New Routing Algorithm for Cyclic Shifts on BRGC Hypercubes. 165-169 BibTeX
• Nen-Fu Huang, Ching-Ho Huang, Yue-Li Wang: A Sweepline Algorithm to Solve the Two-Center Problem. 171-177 BibTeX
• Aldo de Luca, Licia Mione: On Bispecial Factors of the Thue-Morse Word. 179-183 BibTeX
• John H. Leuchner, Les Miller, Giora Slutzki: A Note on the Equivalence of a Set of Egds to a Set of FDs. 185-188 BibTeX
• Kenneth L. Calvert: Eliminating Disjunctions of Leads-to Properties. 189-194 BibTeX
• Gil Neiger: Distributed Consensus Revisited. 195-201 BibTeX
• Dongseung Kim, Joonyoung Park: Two-Way Dominant Sequence Clustering for Processor Scheduling. 203-208 BibTeX
• Eddie Cheng, William H. Cunningham: A Faster Algorithm for Computing the Strength of a Network. 209-212 BibTeX
• Hirotsugu Kakugawa, Satoshi Fujita, Masafumi Yamashita, Tadashi Ae: A Distributed k-Mutual Exclusion Algorithm Using k-Coterie. 213-218 BibTeX

Volume 49, Number 5, 11 March 1994

• Roni Khardon: On Using the Fourier Transform to Learn Disjoint DNF. 219-222 BibTeX
• Wolfgang J. Paul: A Note on Bitonic Sorting. 223-225 BibTeX
• Michiel C. van Wezel, Gerard Tel: An Assertional Proof of Rana's Algorithm. 227-233 BibTeX
• Dany Breslauer: Testing String Superprimitivity in Parallel. 235-241 BibTeX
• Prasoon Tiwari, Martin Tompa: A Direct Version of Shamir and Snir's Lower Bounds on Monotone Circuit Depth. 243-248 BibTeX
• Kaizhong Zhang, Tao Jiang: Some MAX SNP-Hard Results Concerning Unordered Labeled Trees. 249-254 BibTeX
• Mihail N. Kolountzakis: Selection of a Large Sum-Free Subset in Polynomial Time. 255-256 BibTeX
• Lih-Chyau Wuu, Shing-Tsaan Huang: Identity Assignment in Uniform Synchronous Rings. 257-262 BibTeX
• Sriram V. Pemmaraju, Clifford A. Shaffer: Analysis of the Worst Case Space Complexity of a PR Quadtree. 263-267 BibTeX
• Jacek Blazewicz, Paolo Dell'Olmo, Maciej Drozdowski, Maria Grazia Speranza: Corrigendum: Scheduling Multiprocessor Tasks on Three Dedicated Processors. 269-270 BibTeX , ->Inf. Process. Lett. 41(5): 275-280(1992) BibTeX

Volume 49, Number 6, 22 March 1994

• Gerard Tel: Maximal Matching Stabilizes in Quadratic Time. 271-272 BibTeX
• Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. 273-280 BibTeX
• Victor Chepoi, Feodor F. Dragan: Computing a Median Point of a Simple Rectilinear Polygon. 281-285 BibTeX
• Al Borchers, Prosenjit Gupta: Extending the Quadrangle Inequality to Speed-Up Dynamic Programming. 287-290 BibTeX
• Sergio Rajsbaum: Upper and Lower Bounds for Stochastic Marked Graphs. 291-295 BibTeX
• Zeev Collin, Shlomi Dolev: Self-Stabilizing Depth-First Search. 297-301 BibTeX
• G. Sajith, Sanjeev Saxena: Optimal Parallel Algorithms for Coloring Bounded Degree Graphs and Finding Maximal Independent Sets in Rooted Trees. 303-308 BibTeX , Corrigendum: Inf. Process. Lett. 54(5): 305(1995) BibTeX
• Viggo Kann: Maximum Bounded H-Matching is MAX SNP-Complete. 309-318 BibTeX
• Hari N. Reddy, Ernst L. Leiss: An O(log N) Algorithm to Solve Linear Recurrences on Hypercubes. 319-325 BibTeX
• Helmut Prodinger: An Asymptotic Comment on a Paper by Analyti and Pramanik. 327-328 BibTeX