Information Processing Letters, Volume 106

Volume 106, Number 1, March 2008

Krishnendu Chatterjee, Thomas A. Henzinger:
Reduction of stochastic parity to stochastic mean-payoff games. 1-7
Joachim Biskup, David W. Embley, Jan-Hendrik Lochner:
Reducing inference control to access control for normalized database schemas. 8-12
Costas S. Iliopoulos, Mohammad Sohel Rahman:
New efficient algorithms for the LCS and constrained LCS problems. 13-18
Jyh-Jian Sheu, Wen-Tzeng Huang, Chin-Hsing Chen:
Strong diagnosability of regular networks under the comparison model. 19-25
Weiping He, Ing-Ray Chen:
Proxy-based hybrid cache management in Mobile IP systems. 26-32
Iain A. Stewart:
On the fixed-parameter tractability of parameterized model-checking problems. 33-36
George F. Georgakopoulos:
Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying. 37-43

Torben Amtoft:
Slicing for modern program structures: a theory for eliminating irrelevant loops. 45-51
Banghe Li, Yuefeng Shen, Bo Li:
A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation. 52-58
Meijie Ma, Guizhen Liu, Jun-Ming Xu:
The super connectivity of augmented cubes. 59-63
Lun-Min Shih, Chieh-Feng Chiang, Lih-Hsing Hsu, Jimmy J. M. Tan:
Strong Menger connectivity with conditional faults on the class of hypercube-like networks. 64-69
Feifeng Zheng, Yinfeng Xu, E. Zhang:
How much can lookahead help in online single machine scheduling. 70-74
Maxime Crochemore, Lucian Ilie:
Computing Longest Previous Factor in linear time and applications. 75-80
Jiong Guo, Rolf Niedermeier, Johannes Uhlmann:
Two fixed-parameter algorithms for Vertex Covering by Paths on Trees. 81-86

Stephan Westphal:
A note on the k-Canadian Traveller Problem. 87-89
Sèverine Bérard, Cedric Chauve, Christophe Paul:
A more efficient algorithm for perfect sorting by reversals. 90-95
Vincent Vajnovszki:
More restrictive Gray codes for necklaces and Lyndon words. 96-99
Olivier Danvy, Kevin Millikin:
On the equivalence between small-step and big-step abstract machines: a simple application of lightweight fusion. 100-109
Surender Baswana:
Streaming algorithm for graph spanners - single pass and constant processing time per edge. 110-114
Mirko Rahn:
More decidable instances of Post's correspondence problem: beyond counting. 115-119
Thierry Massart, Cédric Meuter, Laurent Van Begin:
On the complexity of partial order trace model checking. 120-126
Adnan Mohamed, R. S. Ramakrishna:
Linear election in pancake graphs. 127-131

Hanna Furmanczyk, Adrian Kosowski, Pawel Zylinski:
A note on mixed tree coloring. 133-135
Gautam K. Das, Subhas C. Nandy:
Weighted broadcast in linear radio networks. 136-143
Josep Díaz, Zvi Lotker, Maria J. Serna:
The distant-2 chromatic number of random proximity and random geometric graphs. 144-148
Attila Bernáth, Gwenaël Joret:
Well-balanced orientations of mixed graphs. 149-151
Jared Saia, Maxwell Young:
Reducing communication costs in robust peer-to-peer networks. 152-158
GaoJun Fan, Shiyao Jin:
A simple coverage-evaluating approach for wireless sensor networks with arbitrary sensing areas. 159-161
Andrzej Szepietowski:
Fooling Turing machines with sublogarithmic space: a note on 'For completeness, sublogarithmic space is no space' by M. Agrawal. 162-163
Arnaud Durand, Miki Hermann:
On the counting complexity of propositional circumscription. 164-170
Beate Bollig:
The optimal read-once branching program complexity for the direct storage access function. 171-174

Tetsuo Kurosaki:
Direct definition of a ternary infinite square-free sequence. 175-179
Sébastien Collette, Liliana Cucu, Joël Goossens:
Integrating job parallelism in real-time scheduling theory. 180-187
Xiaodong Wu:
Efficient intensity map splitting algorithms for intensity-modulated radiation therapy. 188-194
Ivan Rapaport, Karol Suchan, Ioan Todinca:
Minimal proper interval completions. 195-202
Zeev Nutov, Daniel Reichman:
Approximating maximum satisfiable subsystems of linear equations of bounded width. 203-207
Ronen Gradwohl, Amir Yehudayoff:
t-Wise independence with local dependencies. 208-212
Abdullah N. Arslan:
An algorithm with linear expected running time for string editing with substitutions and substring reversals. 213-218
Walter Vogler:
Another short proof of optimality for the MIN cache replacement algorithm. 219-220

J. Francisco Chicano, Enrique Alba:
Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models. 221-231
Shmuel T. Klein:
Should one always use repeated squaring for modular exponentiation? 232-237
Ray J. Solomonoff:
The probability of "undefined" (non-converging) output in generating the universal probability distribution. 238-240
Philippe Moser:
Resource-bounded measure on probabilistic classes. 241-245
Vincent Rijmen, Paulo S. L. M. Barreto, Décio L. Gazzoni Filho:
Rotation symmetry in algebraically generated cryptographic substitution tables. 246-250
Orestis Telelis, Vassilis Zissimopoulos:
Dynamic bottleneck optimization for k-edge and 2-vertex connectivity. 251-257
Aygul Mamut, Elkin Vumar:
Vertex vulnerability parameters of Kronecker products of complete graphs. 258-262