Information Processing Letters, Volume 81

Volume 81, Number 1, 16 January 2002

• Michael Krivelevich:
  Deciding k-colorability in expected polynomial time. 1-6
  
• Vadim V. Lozin:
  On maximum induced matchings in bipartite graphs. 7-11
  
• Kuo-Liang Chung, Wen-Ming Yan:
  Fast 2D discrete cosine transform on compressed image in restricted quadtree and shading format. 13-21
  
• Yaoyun Shi:
  Entropy lower bounds for quantum decision tree complexity. 23-27
  
• Jerzy Skurczynski:
  A characterization of Büchi tree automata. 29-33
  
• Arturo Carpi, Aldo de Luca:
  A combinatorial property of the factor poset of a word. 35-39
  
• Chien-Lung Hsu, Tzong-Sun Wu, Tzong-Chen Wu:
  Improvements of generalization of threshold signature and authenticated encryption for group communications. 41-45
  
• Michael J. Spriggs, J. Mark Keil:
  A new bound for map labeling with uniform circle pairs. 47-53
  
• Alain Bretto, Stéphane Ubéda, Janez Zerovnik:
  A polynomial algorithm for the strong Helly property. 55-57
  

Volume 81, Number 2, 31 January 2002

• Jürgen Branke, Stefan Leppert, Martin Middendorf, Peter Eades:
  Width-restricted layering of acyclic digraphs with consideration of dummy nodes. 59-63
  
• Pascal Koiran:
  Transfer theorems via sign conditions. 65-69
  
• John Noga, Steven S. Seiden, Gerhard J. Woeginger:
  A faster off-line algorithm for the TCP acknowledgement problem. 71-73
  
• Holger Petersen:
  Bounds for the Element Distinctness Problem on one-tape Turing machines. 75-79
  
• Aleksander Bachman, Adam Janiak, Mikhail Y. Kovalyov:
  Minimizing the total weighted completion time of deteriorating jobs. 81-84
  
• Noritaka Kobayashi, Tatsuhiro Tsuchiya, Tohru Kikuno:
  A new method for constructing pair-wise covering designs for software testing. 85-91
  
• R. W. Bulterman, F. W. van der Sommen, Gerard Zwaan, Tom Verhoeff, A. J. M. van Gasteren, W. H. J. Feijen:
  On computing a longest path in a tree. 93-96
  
• Tae-Sun Chung, Hyoung-Joo Kim:
  Extracting indexing information from XML DTDs. 97-103
  
• Wei Lai, Peter Eades:
  Removing edge-node intersections in drawings of graphs. 105-110
  
• Diganta Goswami, Rajib Mall:
  An efficient method for computing dynamic program slices. 111-117
  

Volume 81, Number 3, 14 February 2002

• Jörg Keller:
  A heuristic to accelerate in-situ permutation algorithms. 119-125
  
• Fredrik Jönsson, Thomas Johansson:
  A fast correlation attack on LILI-128. 127-132
  
• Qi Cheng, Fang Fang:
  Kolmogorov random graphs only have trivial stable colorings. 133-136
  
• Joachim Gudmundsson, Thore Husfeldt, Christos Levcopoulos:
  Lower bounds for approximate polygon decomposition and minimum gap. 137-141
  
• Oh-Heum Kwon, Kyung-Yong Chwa:
  Approximation algorithms for general parallel task scheduling. 143-150
  
• Lusheng Wang, Zimao Li:
  An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. 151-156
  
• Hoàng-Oanh Le, Van Bang Le:
  The NP-completeness of (1, r)-subcolorability of cubic graphs. 157-162
  
• Marco Cesati:
  Perfect Code is W[1]-complete. 163-168
  
• Gordon Lyon:
  Comparison of two code scalability tests. 169-174
  

Volume 81, Number 4, 28 February 2002

• Judit Büki, Csaba Szabó:
  Complexity of homomorphisms to direct products of graphs. 175-178
  
• Oukseh Lee, Kwangkeun Yi, Yunheung Paek:
  A proof method for the correctness of modularized 0CFA. 179-185
  
• Toru Araki, Yukio Shibata:
  Pancyclicity of recursive circulant graphs. 187-190
  
• San Skulrattanakulchai:
  4-edge-coloring graphs of maximum degree 3 in linear time. 191-195
  
• Charles U. Martel:
  The expected complexity of Prim's minimum spanning tree algorithm. 197-201
  
• Fanica Gavril:
  Algorithms for maximum weight induced paths. 203-208
  
• Soumen Maity, Bimal K. Roy, Amiya Nayak:
  On enumeration of catastrophic fault patterns. 209-212
  
• Susanne Albers, Marek Karpinski:
  Randomized splay trees: Theoretical and experimental results. 213-221
  
• Alfredo García Olaverri, Ferran Hurtado, Marc Noy, Javier Tejel:
  On the minimum size of visibility graphs. 223-230
  

Volume 81, Number 5, 16 March 2002

• Zenji Kobayashi, Takeshi Sekiguchi:
  On a characterization of the standard Gray code by using its edge type on a hypercube. 231-237
  
• Dong-Ho Lee, Hyoung-Joo Kim:
  An efficient nearest neighbor search in high-dimensional data spaces. 239-246
  
• Refael Hassin, Shlomi Rubinstein:
  A 7/8-approximation algorithm for metric Max TSP. 247-251
  
• Alexander Meduna, Dusan Kolar:
  Homogeneous grammars with a reduced number of non-context-free productions. 253-257
  
• Mark de Berg, A. Frank van der Stappen:
  On the fatness of Minkowski sums. 259-264
  
• Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa:
  Simple algorithms for searching a polygon with flashlights. 265-270
  
• Hai Zhou, Narendra V. Shenoy, William Nicholls:
  Efficient minimum spanning tree construction without Delaunay triangulation. 271-276
  
• Aleksander Vesel, Janez Zerovnik:
  Improved lower bound on the Shannon capacity of C7. 277-282
  
• Nectarios Kitsios, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, John Tsaknakis, Bill Vassiliadis:
  An optimal algorithm for reporting visible rectangles. 283-288
  

Volume 81, Number 6, 31 March 2002

• A. Koubková, Václav Koubek:
  Algorithms for transitive closure. 289-296
  
• Edwin Naroska, Uwe Schwiegelshohn:
  On an on-line scheduling problem for parallel jobs. 297-304
  
• Rezaul Alam Chowdhury, M. Kaykobad, Irwin King:
  An efficient decoding technique for Huffman codes. 305-308
  
• Eric Sopena:
  There exist oriented planar graphs with oriented chromatic number at least sixteen. 309-312
  
• Ilyong Chung, Wankyu Choi, Youngchel Kim, Mike Lee:
  The design of conference key distribution system employing a symmetric balanced incomplete block design. 313-318
  
• Andrew G. Hart, Servet Martínez:
  Sequential iteration of the Erlang fixed-point equations. 319-325
  
• C. T. Ng, T. C. Edwin Cheng, Aleksander Bachman, Adam Janiak:
  Three scheduling problems with deteriorating jobs to minimize the total completion time. 327-333
  
• Bruno Zanuttini, Jean-Jacques Hébrard:
  A unified framework for structure identification. 335-339
  
• Kurt Mehlhorn, Volker Priebe, Guido Schäfer, Naveen Sivadasan:
  All-pairs shortest-paths computation in the presence of negative cycles. 341-343