Information Processing Letters, Volume 86

Volume 86, Number 1, 15 April 2003

Yongsu Park, Tae-Sun Chung, Yookun Cho:
An efficient stream authentication scheme using tree chaining. 1-8
John M. Hitchcock:
Gales suffice for constructive dimension. 9-12
Zakil Koo, Songchun Moon:
Effects of broadcast errors on concurrency control in wireless broadcasting environments. 13-21
Stephen Kwek, Kurt Mehlhorn:
Optimal search for rationals. 23-26
Chung Keung Poon:
Verifying minimum stable circuit values. 27-32
Peter Sanders, Jop F. Sibeyn:
A bandwidth latency tradeoff for broadcast and reduction. 33-38
P. Krishna Reddy, Masaru Kitsuregawa:
Reducing the blocking in two-phase commit with backup sites. 39-47
Rajgopal Kannan, Sudipta Sarangi, Sibabrata Ray, S. Sitharama Iyengar:
Minimal sensor integrity: Measuring the vulnerability of sensor grids. 49-55

Kazuhiro Ogata, Kokichi Futatsugi:
Flaw and modification of the iKP electronic payment protocols. 57-62
Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem. 63-70
Tibor Szabó:
On the spectrum of projective norm-graphs. 71-74
L. Sunil Chandran:
A lower bound for the hitting set size for combinatorial rectangles and an application. 75-78
Yosuke Kikuchi, Yukio Shibata:
On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. 79-85
Daya Ram Gaur, Arvind Gupta, Ramesh Krishnamurti:
A 5/3-approximation algorithm for scheduling vehicles on a path with release and handling times. 87-91
Jau-Der Shih:
Fault-tolerant wormhole routing for hypercube networks. 93-100
Richard C. Brewster, Romeo Rizzi:
On the complexity of digraph packings. 101-106
Scott Effler, Frank Ruskey:
A CAT algorithm for generating permutations with a fixed number of inversions. 107-112

Maciej Kurowski:
Simple and efficient floor-planning. 113-119
Nir Halman:
A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane. 121-128
Camil Demetrescu, Irene Finocchi:
Combinatorial algorithms for feedback problems in directed graphs. 129-136
Axel Born, Cor A. J. Hurkens, Gerhard J. Woeginger:
How to detect a counterfeit coin: Adaptive versus non-adaptive solutions. 137-141
Beate Bollig:
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs. 143-148
Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem. 149-154
Loon-Been Chen:
An efficient minimum and maximum global snapshot algorithm. 155-159
Andreas Brandstädt, Hoàng-Oanh Le, Jean-Marie Vanherpe:
Structure and stability number of chair-, co-P- and gem-free graphs revisited. 161-167

Roy Friedman, Roman Vitenberg, Gregory Chockler:
On the composability of consistency conditions. 169-176
Li Lin, Yunfei Jiang:
The computation of hitting sets: Review and new algorithms. 177-184
Hsun-Jung Cho, Li-Yen Hsu:
Generalized honeycomb torus. 185-190
Rastislav Kralovic, Peter Ruzicka:
Minimum feedback vertex sets in shuffle-based interconnection networks. 191-196
Susanne E. Hambrusch, Chuan-Ming Liu:
Data replication in static tree structures. 197-202
Esther M. Arkin, Joseph S. B. Mitchell, Christine D. Piatko:
Minimum-link watchman tours. 203-207
Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas:
Reflected min-max heaps. 209-214
Luc Devroye, Pat Morin:
Cuckoo hashing: Further analysis. 215-219
Stefan D. Bruda, Selim G. Akl:
On limits on the computational power of data-accumulating algorithms. 221-227

Rafiqul Islam, Nasim Adnan, Nur Islam, Shohorab Hossen:
A new external sorting algorithm with no additional disk space. 229-233
Henning Fernau, Alexander Meduna:
A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. 235-240
Sabrina Mantaci, Antonio Restivo, Marinella Sciortino:
Burrows-Wheeler transform and Sturmian words. 241-246
Alexander Okhotin:
The hardest linear conjunctive language. 247-253
Marc Chemillier, Charlotte Truchet:
Computation of words satisfying the "rhythmic oddity property" (after Simha Arom's works). 255-261
Shin-Shin Kao, Lih-Hsing Hsu:
Brother trees: A family of optimal 1_p-hamiltonian and 1-edge hamiltonian graphs. 263-269
Chun-Nan Hung, Hong-Chun Hsu, Kao-Yung Liang, Lih-Hsing Hsu:
Ring embedding in faulty pancake graphs. 271-275
Leonid Libkin:
A collapse result for constraint queries over structures of small degree. 277-281
Manuel Abellanas, Ferran Hurtado, Vera Sacristan, Christian Icking, Lihong Ma, Rolf Klein, Elmar Langetepe, Belén Palop:
Voronoi Diagram for services neighboring a highway. 283-288

Jer-Shyan Wu, Yu-Kuo Wang:
An optimal algorithm to implement the Hanoi towers with parallel moves. 289-293
Zuhua Shao:
Cryptanalysis of "an identity-based society oriented signature scheme with anonymous signers". 295-298
Joe Sawada, Jeremy Spinrad:
From a simple elimination ordering to a strong elimination ordering in linear time. 299-302
Brad Lushman, Gordon V. Cormack:
Proof of correctness of Ressel's adOPTed algorithm. 303-310
Alain Hertz, Vadim V. Lozin, David Schindl:
Finding augmenting chains in extensions of claw-free graphs. 311-316
Christian Igel, Marc Toussaint:
On classes of functions for which No Free Lunch results hold. 317-321
Shahrokh Saeednia:
A note on Girault's self-certified model. 323-327
Jonathan K. Millen:
On the freedom of decryption. 329-333
Romeo Rizzi:
On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic. 335-338
Sung Kwon Kim:
Linear-time algorithm for finding a maximum-density segment of a sequence. 339-342