Information Processing Letters, Volume 90

Volume 90, Number 1, 15 April 2004

• Andrzej Tarlecki:
  Editorial. 1-2
  
• Nicolas Markey, Ph. Schnoebelen:
  A PTIME-complete matching problem for SLP-compressed words. 3-6
  
• Neal Lesh, Joe Marks, A. McMahon, Michael Mitzenmacher:
  Exhaustive approaches to 2D rectangular perfect packings. 7-14
  
• Shao Chin Sung, Keisuke Tanaka:
  Limiting negations in bounded-depth circuits: An extension of Markov's theorem. 15-20
  
• Stavros Tripakis:
  Undecidable problems of decentralized observation and control on regular languages. 21-28
  
• Razvan Diaconescu:
  Herbrand theorems in arbitrary institutions. 29-37
  
• Roy Friedman, Achour Mostéfaoui, Michel Raynal:
  A weakest failure detector-based asynchronous consensus protocol for f<n. 39-46
  
• Mahesh Kallahalla, Peter J. Varman:
  Analysis of simple randomized buffer management for parallel I/O. 47-52
  

Volume 90, Number 2, 30 April 2004

• Vicent Cholvi, Josep Bernabéu:
  Relationships between memory models. 53-58
  
• Toshihiro Fujito, Takashi Doi:
  A 2-approximation NC algorithm for connected vertex cover and tree cover. 59-63
  
• Ioannis N. Kouris, Christos Makris, Athanasios K. Tsakalidis:
  Efficient automatic discovery of 'hot' itemsets. 65-72
  
• Abdullah AlWehaibi, Michel Kadoch, Anjali Agarwal, Ahmed K. Elhakeem:
  Packet loss probability for DiffServ over IP and MPLS reliable homogeneous multicast networks. 73-80
  
• Hongfei Sui, Jianxin Wang, Jianer Chen, Songqiao Chen:
  The cost of becoming anonymous: on the participant payload in Crowds. 81-86
  
• Eurípides Montagne, Anand Ekambaram:
  An optimal storage format for sparse matrices. 87-92
  
• Ding Liu:
  A note on point location in arrangements of hyperplanes. 93-95
  
• Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani:
  A note on 3D orthogonal drawings with direction constrained edges. 97-101
  

Volume 90, Number 3, 16 May 2004

• A. Savelli:
  On numerically decipherable codes and their homophonic partitions. 103-108
  
• Iordanis Kerenidis, Ronald de Wolf:
  Quantum symmetrically-private information retrieval. 109-114
  
• Kazuo Iwama, Kouki Yonezawa:
  The orthogonal CNN problem. 115-120
  
• Evangelos Kranakis, Danny Krizanc, Sunil M. Shende:
  Approximate hotlink assignment. 121-128
  
• Joan M. Lucas:
  A direct algorithm for restricted rotation distance. 129-134
  
• Gabriel Nivasch:
  Cycle detection using a stack. 135-140
  
• Sergey Bereg:
  Transforming pseudo-triangulations. 141-145
  
• Jin-yi Cai, Osamu Watanabe:
  Relativized collapsing between BPP and PH under stringent oracle access. 147-154
  
• Yih-Ching Su, Chu-Sing Yang, Chen-Wei Lee:
  The analysis of packet loss prediction for Gilbert-model with loss rate uplink. 155-159
  

Volume 90, Number 4, 31 May 2004

• Ernst-Erich Doberkat:
  Factoring stochastic relations. 161-166
  
• Valerio Freschi, Alessandro Bogliolo:
  Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism. 167-173
  
• Francis Y. L. Chin, Alfredo De Santis, Anna Lisa Ferrara, N. L. Ho, S. K. Kim:
  A simple algorithm for the constrained sequence problems. 175-179
  
• James F. Korsh, Paul LaFollette:
  Constant time generation of derangements. 181-186
  
• Alexandros V. Gerbessiotis, Constantinos J. Siniolakis:
  Probabilistic integer sorting. 187-193
  
• Harumichi Nishimura, Tomoyuki Yamakami:
  Polynomial time quantum computation with advice. 195-204
  
• Nicholas J. A. Harvey, J. Ian Munro:
  Deterministic SkipNet. 205-208
  
• Guy Melançon, Fabrice Philippe:
  Generating connected acyclic digraphs uniformly at random. 209-213
  

Volume 90, Number 5, 15 June 2004

• Jean-Loup Guillaume, Matthieu Latapy:
  Bipartite structure of all complex networks. 215-221
  
• Mads Sig Ager, Olivier Danvy, Jan Midtgaard:
  A functional correspondence between call-by-need evaluators and lazy abstract machines. 223-232
  
• David P. Bunde:
  SPT is optimally competitive for uniprocessor flow. 233-238
  
• Petra Sparl, Janez Zerovnik:
  2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs. 239-246
  
• Richard Parker, Andrew Plater:
  Addition chains with a bounded number of registers. 247-252
  
• Sang-Wook Kim, Dae-Hyun Park, Heon-Gil Lee:
  Efficient processing of subsequence matching with the Euclidean metric in time-series databases. 253-260
  
• Carme Àlvarez, Maria J. Blesa, Josep Díaz, Antonio Fernández, Maria J. Serna:
  The complexity of deciding stability under FFS in the Adversarial Queueing model. 261-266
  
• Mark Weston:
  A fixed-parameter tractable algorithm for matrix domination. 267-272
  

Volume 90, Number 6, 30 June 2004

• Joachim Breit:
  An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. 273-278
  
• Maw-Shang Chang, Chin-Hua Lin, Chuan-Min Lee:
  New upper bounds on feedback vertex numbers in butterflies. 279-285
  
• Robert M. Hierons:
  Using a minimal number of resets when testing from a finite state machine. 287-292
  
• Mingjun Ji, Huanwen Tang, Juan Guo:
  A single-point mutation evolutionary programming. 293-299
  
• Hana Chockler, Dan Gutfreund:
  A lower bound for testing juntas. 301-305
  
• Stavros D. Nikolopoulos, Christos Nomikos, Panos Rondogiannis:
  A limit characterization for the number of spanning trees of graphs. 307-313