Information Processing Letters, Volume 61

Volume 61, Number 1, 14 January 1997

• Yongge Wang:
  NP-Hard Sets are Superterse Unless NP is Small. 1-6
  
• Martin Farach, S. Muthukrishnan:
  Optimal Parallel Randomized Renaming. 7-10
  
• Gow-Hsing King, Wen-Guey Tzeng:
  On-Line Algorithms for the Dominating Set Problem. 11-14
  
• Jacob Kornerup:
  Odd-Even Sort in Powerlists. 15-24
  
• Toru Hasunuma, Yukio Shibata:
  Containment of Butterflies in Networks Constructed by the Line Digraph Operation. 25-30
  
• Sidi Mohamed Sedjelmaci, Christian Lavault:
  Improvements on the Accelerated Integer GCD Algorithm. 31-36
  
• Panayiotis Bozanis, Nectarios Kitsios, Christos Makris, Athanasios K. Tsakalidis:
  The Space-Optimal Version of a Known Rectangle Enclosure Reporting Algorithm. 37-41
  
• Yaagoub Ashir, Iain A. Stewart, Aqeel Ahmed:
  Communication Algorithms in k-Ary n-Cube Interconnection Networks. 43-48
  
• Avrim Blum, David R. Karger:
  An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs. 49-53
  
• Steve Taylor, Nabil I. Hachem, Stanley M. Selkow:
  The Average Height of a Node in the BANG Abstract Directory Tree. 55-61
  

Volume 61, Number 2, 28 January 1997

• Richard Zippel:
  Zero Testing of Algebraic Functions. 63-67
  
• Bernd Loescher:
  One Unary Function Says Less Than Two in Existential Second Order Logic. 69-75
  
• D. J. Guan, Xuding Zhu:
  A Coloring Problem for Weighted Graphs. 77-81
  
• Ryuhei Uehara:
  Collapse of PP with a Semi-Random Source to BPP. 83-87
  
• Youssef Saab:
  An Improved Algorithm for Intersecting Convex Polygons. 89-90
  
• Kayoko Shikishima-Tsuji, Masashi Katsura, Yuji Kobayashi:
  On Termination of Confluent One-Rule String-Rewriting Systems. 91-96
  
• Kuo-Ling Chung:
  Efficient Huffman Decoding. 97-99
  
• Hans L. Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki:
  It is Hard to Know when Greedy is Good for Finding Independent Sets. 101-111
  
• Chin Lung Lu, Chuan Yi Tang:
  A Linear-Time Algorithm for the Weighted Feedback Vertex Problem on Interval Graphs. 107-111
  
• Paolo Giulio Franciosa, Giorgio Gambosi, Umberto Nanni:
  The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs. 113-120
  

Volume 61, Number 3, February 1997

• Jitender S. Deogun, Dieter Kratsch, George Steiner:
  An Approximation Algorithm for Clustering Graphs with Dominating Diametral Path. 121-127
  
• Thierry Lecroq, Guillaume Luce, Jean Frédéric Myoupo:
  A Faster Linear Systolic Algorithm for Recovering a Longest Common Subsequence. 129-136
  
• Raffaele Mosca:
  Polynomial Algorithms for the Maximum Stable Set Problem on Particular Classes of P_5-Free Graphs. 137-143
  
• Guochuan Zhang:
  A Simple Semi On-Line Algorithm for P2//C_{max} with a Buffer. 145-148
  
• Seok-Hee Hong, Myoung-Ho Kim:
  Resolving Data Conflicts with Multiple Versions and Precedence Relationships in Real-Time Databases. 149-156
  
• Ivan Fris, Ivan Havel, Petr Liebl:
  The Diameter of the Cube-Connected Cycles. 157-160
  
• Arnold Rosenbloom:
  Monotone Real Circuits are More Powerful than Monotone Boolean Circuits. 161-164
  
• M. Z. Wang:
  Linear Complexity Profiles and Jump Complexity. 165-168
  
• Tadakazu Sato:
  Ergodicity of Linear Cellular Automata over ganzen Zahlen_m. 169-172
  

Volume 61, Number 4, 28 February 1997

• Shih-Yih Wang, Lih-Hsing Hsu, Ting-Yi Sung:
  Faithful 1-Edge Fault Tolerant Graphs. 173-181
  
• Martin Henk:
  Note on Shortest and Nearest Lattice Vectors. 183-188
  
• Patrizio Cintioli, Riccardo Silvestri:
  Revisiting a Result of Ko. 189-194
  
• Paolo Dell'Olmo, Stefano Giordani, Maria Grazia Speranza:
  An Approximation Result for a Duo-Processor Task Scheduling Problem. 195-200
  
• Mark J. Encarnación:
  Black-Box Polynomials Resultants. 201-204
  
• Frédéric Roupin:
  On Approximating the Memory-Constrained Module Allocation Problem. 205-208
  
• Sung-Mo Park, Sangjin Lee, Soo Hak Sung, Kwangjo Kim:
  Improving Bounds for the Number of Correlation Immune Boolean Functions. 209-212
  
• Ying Choi, Tak Wah Lam:
  Dynamic Suffix Tree and Two-Dimensional Texts Management. 213-220
  
• Priyalal Kulasinghe:
  Connectivity of the Crossed Cube. 221-226
  

Volume 61, Number 5, 14 March 1997

• Dimitrios M. Thilikos, Hans L. Bodlaender:
  Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems. 227-232
  
• Antoni W. Mazurkiewicz:
  Distributed Enumeration. 233-239
  
• Joseph M. Morris:
  Non-Deterministic Expressions and Predicate Transformers. 241-246
  
• Tiziana Calamoneri, Rossella Petreschi:
  A New 3D Representation of Trivalent Cayley Networks. 247-252
  
• Jean Frédéric Myoupo, Ahmad Wabbi:
  Improved Linear Systolic Algorithms for Substring Statistics. 253-258
  
• C. Micheneau:
  Disjoint Hamiltonian Cycles in Recursive Circulant Graphs. 259-264
  
• Kazuo Iwama, Chuzo Iwamoto, T. Ohsawa:
  A Faster Parallel Algorithm for k-Connectivity. 265-269
  
• Knut Verbarg:
  Approximate Center Points in Dense Point Sets. 271-278
  
• Berry Schoenmakers:
  A Tight Lower Bound for Top-Down Skew Heaps. 279-284
  

Volume 61, Number 6, 28 March 1997

• Devendra Kumar, Abraham Silberschatz:
  A Counter-Example to an Algorithm for the Generalized Input-Output Construct of CSP. 287
  
• Eyal Kushilevitz:
  A Simple Algorithm for Learning O (log n)-Term DNF. 289-292
  
• Louis Ibarra:
  Finding Pattern Matchings for Permutations. 293-295
  
• Moshe Dror, Wieslaw Kubiak, Paolo Dell'Olmo:
  Scheduling Chains to Minimize Mean Flow Time. 297-301
  
• Nader H. Bshouty:
  On Learning Multivariate Polynomials Under the Uniform Distribution. 303-309
  
• H. S. Chao, Fang-Rong Hsu, Richard C. T. Lee:
  An Optimal EREW Parallel Algorithm for Computing Breadth-First Search Trees on Permutation Graphs. 311-316
  
• Jianer Chen, Saroja P. Kanchi, Arkady Kanevsky:
  A Note on Approximating Graph Genus. 317-322
  
• Athena Vakali, Yannis Manolopoulos:
  An Exact Analysis on Expected Seeks in Shadowed Disks. 323-329
  
• Paola Flocchini:
  Minimal Sense of Direction in Regular Networks. 331-338