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
Electronic Edition (link) BibTeX
John M. Hitchcock:
Gales suffice for constructive dimension. 9-12
Electronic Edition (link) BibTeX
Zakil Koo, Songchun Moon:
Effects of broadcast errors on concurrency control in wireless broadcasting environments. 13-21
Electronic Edition (link) BibTeX
Stephen Kwek, Kurt Mehlhorn:
Optimal search for rationals. 23-26
Electronic Edition (link) BibTeX
Chung Keung Poon:
Verifying minimum stable circuit values. 27-32
Electronic Edition (link) BibTeX
Peter Sanders, Jop F. Sibeyn:
A bandwidth latency tradeoff for broadcast and reduction. 33-38
Electronic Edition (link) BibTeX
P. Krishna Reddy, Masaru Kitsuregawa:
Reducing the blocking in two-phase commit with backup sites. 39-47
Electronic Edition (link) BibTeX
Rajgopal Kannan, Sudipta Sarangi, Sibabrata Ray, S. Sitharama Iyengar:
Minimal sensor integrity: Measuring the vulnerability of sensor grids. 49-55
Electronic Edition (link) BibTeX

Kazuhiro Ogata, Kokichi Futatsugi:
Flaw and modification of the iKP electronic payment protocols. 57-62
Electronic Edition (link) BibTeX
Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem. 63-70
Electronic Edition (link) BibTeX
Tibor Szabó:
On the spectrum of projective norm-graphs. 71-74
Electronic Edition (link) BibTeX
L. Sunil Chandran:
A lower bound for the hitting set size for combinatorial rectangles and an application. 75-78
Electronic Edition (link) BibTeX
Yosuke Kikuchi, Yukio Shibata:
On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. 79-85
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Jau-Der Shih:
Fault-tolerant wormhole routing for hypercube networks. 93-100
Electronic Edition (link) BibTeX
Richard C. Brewster, Romeo Rizzi:
On the complexity of digraph packings. 101-106
Electronic Edition (link) BibTeX
Scott Effler, Frank Ruskey:
A CAT algorithm for generating permutations with a fixed number of inversions. 107-112
Electronic Edition (link) BibTeX

Maciej Kurowski:
Simple and efficient floor-planning. 113-119
Electronic Edition (link) BibTeX
Nir Halman:
A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane. 121-128
Electronic Edition (link) BibTeX
Camil Demetrescu, Irene Finocchi:
Combinatorial algorithms for feedback problems in directed graphs. 129-136
Electronic Edition (link) BibTeX
Axel Born, Cor A. J. Hurkens, Gerhard J. Woeginger:
How to detect a counterfeit coin: Adaptive versus non-adaptive solutions. 137-141
Electronic Edition (link) BibTeX
Beate Bollig:
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs. 143-148
Electronic Edition (link) BibTeX
Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem. 149-154
Electronic Edition (link) BibTeX
Loon-Been Chen:
An efficient minimum and maximum global snapshot algorithm. 155-159
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

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

Rafiqul Islam, Nasim Adnan, Nur Islam, Shohorab Hossen:
A new external sorting algorithm with no additional disk space. 229-233
Electronic Edition (link) BibTeX
Henning Fernau, Alexander Meduna:
A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. 235-240
Electronic Edition (link) BibTeX
Sabrina Mantaci, Antonio Restivo, Marinella Sciortino:
Burrows-Wheeler transform and Sturmian words. 241-246
Electronic Edition (link) BibTeX
Alexander Okhotin:
The hardest linear conjunctive language. 247-253
Electronic Edition (link) BibTeX
Marc Chemillier, Charlotte Truchet:
Computation of words satisfying the "rhythmic oddity property" (after Simha Arom's works). 255-261
Electronic Edition (link) BibTeX
Shin-Shin Kao, Lih-Hsing Hsu:
Brother trees: A family of optimal 1_p-hamiltonian and 1-edge hamiltonian graphs. 263-269
Electronic Edition (link) BibTeX
Chun-Nan Hung, Hong-Chun Hsu, Kao-Yung Liang, Lih-Hsing Hsu:
Ring embedding in faulty pancake graphs. 271-275
Electronic Edition (link) BibTeX
Leonid Libkin:
A collapse result for constraint queries over structures of small degree. 277-281
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

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