Information Processing Letters, Volume 87

Volume 87, Number 1, 16 July 2003

• Uriel Feige, Orly Yahalom:
  On the complexity of finding balanced oneway cuts. 1-5
  
• Jörg Rothe:
  Exact complexity of Exact-Four-Colorability. 7-12
  
• Friedrich Eisenbrand, Fabrizio Grandoni:
  Detecting directed 4-cycles still faster. 13-15
  
• Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir:
  A note on an expressiveness hierarchy for multi-exit iteration. 17-23
  
• Beate Bollig, Ingo Wegener:
  Functions that have read-once branching programs of quadratic size are not necessarily testable. 25-29
  
• Jae-Hoon Kim, Kyung-Yong Chwa:
  Non-clairvoyant scheduling for weighted flow time. 31-37
  
• Amir M. Ben-Amram:
  Tighter constant-factor time hierarchies. 39-44
  
• Chung-Shou Liao, Gerard J. Chang:
  k-tuple domination in graphs. 45-50
  
• Guillaume Fertin, Emmanuel Godard, André Raspaud:
  Acyclic and k-distance coloring of the grid. 51-58
  

Volume 87, Number 2, 31 July 2003

• Robert A. Hochberg, Matthias F. M. Stallmann:
  Optimal one-page tree embeddings in linear time. 59-66
  
• Salvatore Ruggieri:
  On computing the semi-sum of two integers. 67-71
  
• Richard Nock, Tapio Elomaa, Matti Kääriäinen:
  Reduced Error Pruning of branching programs cannot be approximated to within a logarithmic factor. 73-78
  
• Harry Buhrman, Ronald de Wolf:
  Quantum zero-error algorithms cannot be composed. 79-84
  
• Michael L. Fredman:
  The number of tests required to search an unordered table. 85-88
  
• Chin-Chia Wu, Wen-Chiung Lee:
  Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine. 89-93
  
• Khaled A. S. Abdel-Ghaffar:
  Maximum number of edges joining vertices on a cube. 95-99
  
• Minghui Jiang, Jianbo Qian, Zhongping Qin, Binhai Zhu, Robert J. Cimikowski:
  A simple factor-3 approximation for labeling points with circles. 101-105
  
• Tseng-Kuei Li, Chang-Hsiung Tsai, Jimmy J. M. Tan, Lih-Hsing Hsu:
  Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. 107-110
  
• Kazuyuki Amano, Kazuo Iwama, Akira Maruoka, Kenshi Matsuo, Akihiro Matsuura:
  Inclusion-exclusion for k-CNF formulas. 111-117
  

Volume 87, Number 3, 16 August 2003

• Maxime Crochemore, Valery T. Stefanov:
  Waiting time and complexity for matching patterns with automata. 119-125
  
• Dominique de Werra, Pierre Hansen:
  Using stable sets to bound the chromatic number. 127-131
  
• Sven Hartmann, Anne Hoffmann, Sebastian Link, Klaus-Dieter Schewe:
  Axiomatizing functional dependencies in the Higher-Order Entity-Relationship Model. 133-137
  
• Bruce E. Litow:
  Inequality of finite behaviors of rational weight finite automata is in R. 139-145
  
• Michel Habib, Emmanuelle Lebhar, Christophe Paul:
  A note on finding all homogeneous set sandwiches. 147-151
  
• B. S. Panda, Sajal K. Das:
  A linear time recognition algorithm for proper interval graphs. 153-161
  
• Pranava K. Jha:
  Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh. 163-168
  
• Olivier Markowitch, Shahrokh Saeednia:
  Cryptanalysis of the Wu-Varadhrajan fair exchange protocol. 169-171
  

Volume 87, Number 4, 31 August 2003

• Jean Marcel Pallo:
  Right-arm rotation distance between binary trees. 173-177
  
• Xuehou Tan, Tomio Hirata:
  Finding shortest safari routes in simple polygons. 179-186
  
• Jean H. Gallier, Salvatore La Torre, Supratik Mukhopadhyay:
  Deterministic finite automata with recursive calls and DPDAs. 187-193
  
• L. Sunil Chandran, C. R. Subramanian:
  A spectral lower bound for the treewidth of a graph and its consequences. 195-200
  
• Kimmo Fredriksson:
  Shift-or string matching with super-alphabets. 201-204
  
• Kwanghoon Choi, Taisook Han:
  A type system for the push-enter model. 205-211
  
• Wil Michiels, Jan H. M. Korst:
  Complexity of min-max subsequence problems. 213-217
  
• Bernhard Fuchs:
  A note on the terminal Steiner tree problem. 219-220
  
• Ho-Sook Kim, Hwan-Seung Yong:
  Personalized cache management for mobile computing environments. 221-228
  

Volume 87, Number 5, 15 September 2003

• Philip M. Long:
  An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution. 229-234
  
• Manuel Hernández, David A. Rosenblueth:
  Disjunctive partial deduction of a right-to-left string-matching algorithm. 235-241
  
• Punit Chandra, Ajay D. Kshemkalyani:
  Distributed algorithm to detect strong conjunctive predicates. 243-249
  
• Stephen T. Hedetniemi, David Pokrass Jacobs, Pradip K. Srimani:
  Linear time self-stabilizing colorings. 251-255
  
• Yon Dohn Chung, Jong Wook Kim, Myoung-Ho Kim:
  Efficient preprocessing of XML queries using structured signatures. 257-264
  
• Florent Jacquemard:
  Reachability and confluence are undecidable for flat term rewriting systems. 265-270
  
• Sing-Ling Lee, Hann-Jang Ho:
  On minimizing the maximum congestion for Weighted Hypergraph Embedding in a Cycle. 271-275
  
• Kilsoo Chun, Seungjoo Kim, Sangjin Lee, Soo Hak Sung, Seonhee Yoon:
  Differential and linear cryptanalysis for 2-round SPNs. 277-282
  

Volume 87, Number 6, 30 September 2003

• Bruce E. Litow:
  A note on commutative multivariate rational series. 283-285
  
• Michael Hoffmann, Csaba D. Tóth:
  Alternating paths through disjoint line segments. 287-294
  
• Juan Luis Esteban, Jacobo Torán:
  A combinatorial characterization of treelike resolution space. 295-300
  
• Håkan Jonsson:
  An approximative solution to the Zookeeper's Problem. 301-307
  
• Salem Derisavi, Holger Hermanns, William H. Sanders:
  Optimal state-space lumping in Markov chains. 309-315
  
• Ting-Yem Ho, Jou-Ming Chang:
  Sorting a sequence of strong kings in a tournament. 317-320
  
• Anna Gál, Pavel Pudlák:
  A note on monotone complexity and the rank of matrices. 321-326
  
• Benedetto Intrigila, Monica Nesi:
  On structural properties of eta-expansions of identity. 327-333