Information Processing Letters, Volume 89

Volume 89, Number 1, 16 January 2004

• Ruggero Lanotte, Andrea Maggiolo-Schettini, Simone Tini:
  Epsilon-transitions in Concurrent Timed Automata. 1-7
  
• Iiro S. Honkala, Tero Laihonen:
  On identifying codes in the hexagonal mesh. 9-14
  
• Doratha E. Drake, Stefan Hougardy:
  On approximation algorithms for the terminal Steiner tree problem. 15-18
  
• Timothy M. Chan:
  A note on maximum independent sets in rectangle intersection graphs. 19-23
  
• Millist W. Vincent, Jixue Liu:
  Irrelevant updates and self-maintainability in transitive closure database views. 25-29
  
• Floris Geerts, Bart Kuijpers:
  Topological formulation of termination properties of iterates of functions. 31-35
  
• Gunter Grieser, Steffen Lange:
  Incremental learning of approximations from positive data. 37-42
  
• N. V. Vinodchandran:
  AM_exp[nsube](NP[cap]coNP)/poly. 43-47
  
• Bruce K. Durgan:
  Compact searchable static binary trees. 49-52
  

Volume 89, Number 2, 31 January 2004

• Suzanne M. Seager:
  The greedy algorithm for domination in graphs of maximum degree 3. 53-56
  
• Rudolf Fleischer, Mordecai J. Golin, Chin-Tau A. Lea, Steven Wong:
  Finding optimal paths in MREP routing. 57-63
  
• Wojciech Fraczak, Anna Podolak:
  A characterization of s-languages. 65-70
  
• Stasys Jukna:
  On the minimum number of negations leading to super-polynomial savings. 71-74
  
• Ralf Klasing, Christian Laforest:
  Hardness results and approximation algorithms of k-tuple domination in graphs. 75-83
  
• Dániel Marx:
  List edge multicoloring in graphs with few cycles. 85-90
  
• Sasanka Roy, Partha P. Goswami, Sandip Das, Subhas C. Nandy:
  Optimal algorithm for a special point-labeling problem. 91-98
  
• Paul Valiant:
  The Log-Rank Conjecture and low degree polynomials. 99-103
  

Volume 89, Number 3, 14 February 2004

• L. Sunil Chandran:
  Minimum cuts, girth and a spectral threshold. 105-110
  
• Florian Hess:
  On the security of the verifiably-encrypted signature scheme of Boneh, Gentry, Lynn and Shacham. 111-114
  
• Joo-Won Jung, Kyung-Yong Chwa:
  Labeling points with given rectangles. 115-121
  
• Christel Baier, Holger Hermanns, Joost-Pieter Katoen:
  Probabilistic weak simulation is decidable in polynomial time. 123-130
  
• Iordanis Kerenidis, Ashwin Nayak:
  Weak coin flipping with small bias. 131-135
  
• Boaz Ben-Moshe, Paz Carmi, Matthew J. Katz:
  Computing all large sums-of-pairs in _Rⁿ and the discrete planar two-watchtower problem. 137-139
  
• Thomas Perst, Helmut Seidl:
  Macro forest transducers. 141-149
  
• Guilherme Dias da Fonseca, Celina M. Herrera de Figueiredo, Paulo Cezar Pinto Carvalho:
  Kinetic hanger. 151-157
  

Volume 89, Number 4, 28 February 2004

• Manoel B. Campêlo, Ricardo C. Corrêa, Yuri Frota:
  Cliques, holes and the vertex coloring polytope. 159-164
  
• Andreas Brandstädt, Van Bang Le, H. N. de Ridder:
  Efficient robust algorithms for the Maximum Weight Stable Set Problem in chair-free graph classes. 165-173
  
• Pierluigi Crescenzi, Federico Greco:
  The minimum likely column cover problem. 175-179
  
• András Kovács, Tamás Kis:
  Partitioning of trees for minimizing height and cardinality. 181-185
  
• Leroy Johnson:
  Tumble, a fast simple iteration algorithm for Fibonacci. 187-189
  
• Salvador Lucas:
  Strong and NV-sequentiality of constructor systems. 191-201
  
• Fu-Hsing Wang, Yue-Li Wang, Jou-Ming Chang:
  Feedback vertex sets in star graphs. 203-208
  
• Ciprian Doru Giurcaneanu:
  On some properties of the NML estimator for Bernoulli strings. 209-213
  

Volume 89, Number 5, 16 March 2004

• Bruno Codenotti, Gianluca De Marco, Mauro Leoncini, Manuela Montangero, Massimo Santini:
  Approximation algorithms for a hierarchically structured bin packing problem. 215-221
  
• Hiroshi Nagamochi, Takahisa Suzuki, Toshimasa Ishii:
  A simple recognition of maximal planar graphs. 223-226
  
• Guilin Wang:
  Universal forgery on a group signature scheme using self-certified public keys. 227-231
  
• Vladlen Koltun:
  Ready, Set, Go! The Voronoi diagram of moving points that start from a line. 233-235
  
• Jérôme Durand-Lose:
  A Kleene theorem for splitable signals. 237-245
  
• Irit Dinur, Shmuel Safra:
  On the hardness of approximating label-cover. 247-254
  
• Elias Dahlhaus, Peter Dankelmann, R. Ravi:
  A linear-time algorithm to compute a MAD tree of an interval graph. 255-259
  
• Harald Fecher:
  A completed hierarchy of true concurrent equivalences. 261-265
  

Volume 89, Number 6, 31 March 2004

• Hendrik Jan Hoogeboom, Walter A. Kosters:
  Tetris and decidability. 267-272
  
• Nikolaos Laoutaris, Vassilis Zissimopoulos, Ioannis Stavrakakis:
  Joint object placement and node dimensioning for Internet content distribution. 273-279
  
• Mayer Goldberg:
  A construction of one-point bases in extended lambda calculi. 281-286
  
• Yung-Ling Lai, Gerard J. Chang:
  On the profile of the corona of two graphs. 287-292
  
• Hemangee K. Kapoor, Mark B. Josephs:
  Modelling and verification of delay-insensitive circuits using CCS and the Concurrency Workbench. 293-296
  
• Maciej Liskiewicz, Bodo Manthey:
  New lower and upper bounds for the competitive ratio of transmission protocols. 297-301
  
• Laurent Alonso, Philippe Chassaing, Edward M. Reingold, René Schott:
  The worst-case chip problem. 303-308
  
• Tetsuo Yokoyama, Zhenjiang Hu, Masato Takeichi:
  Deterministic second-order patterns. 309-314