Information Processing Letters, Volume 84

Volume 84, Number 1, 16 October 2002

Elvira Mayordomo:
A Kolmogorov complexity characterization of constructive Hausdorff dimension. 1-3
Electronic Edition (link) BibTeX
Mauricio Ayala-Rincón, Alexsandro F. da Fonseca, Haydée Werneck Poubel, José de Siqueira:
A framework to visualize equivalences between computational models of regular languages. 5-16
Electronic Edition (link) BibTeX
Takeshi Kanda, Kokichi Sugihara:
Comparison of various trees for nearest-point search with/without the Voronoi diagram. 17-22
Electronic Edition (link) BibTeX
Shivi Shekhar Bansal, Bijendra Vishal, Phalguni Gupta:
Near optimal Cholesky factorization on orthogonal multiprocessors. 23-30
Electronic Edition (link) BibTeX
Jun Gu, Xiao-Dong Hu, Mu-Hong Zhang:
Algorithms for multicast connection under multi-path routing model. 31-39
Electronic Edition (link) BibTeX
Ronald I. Greenberg, Lee Guan:
On the area of hypercube layouts. 41-46
Electronic Edition (link) BibTeX
Yong-Jik Kim, James H. Anderson:
A space- and time-efficient local-spin spin lock. 47-55
Electronic Edition (link) BibTeX

Juha Honkala:
The equality problem for Parikh simple algebraic power series. 57-60
Electronic Edition (link) BibTeX
Gregory Karagiorgos, Nikolaos M. Missirlis:
Accelerated diffusion algorithms for dynamic load balancing. 61-67
Electronic Edition (link) BibTeX
Lars Jacobsen, Kim S. Larsen, Morten N. Nielsen:
On the existence and construction of non-extreme (a, b)-trees. 69-73
Electronic Edition (link) BibTeX
Patricia Bouyer:
A logical characterization of data languages. 75-85
Electronic Edition (link) BibTeX
Yen-Chu Chuang, Lih-Hsing Hsu, Chung-Haw Chang:
Optimal 1-edge fault-tolerant designs for ladders. 87-92
Electronic Edition (link) BibTeX
Anand Srinivasan, Sanjoy K. Baruah:
Deadline-based scheduling of periodic task systems on multiprocessors. 93-98
Electronic Edition (link) BibTeX
Yingyu Wan, Guoliang Chen, Yinlong Xu:
A note on the minimum label spanning tree. 99-101
Electronic Edition (link) BibTeX
Guo-Hui Lin, Guoliang Xue:
On the terminal Steiner tree problem. 103-107
Electronic Edition (link) BibTeX
Oh-Heum Kwon:
Scheduling time-constrained multicast messages in circuit-switched tree networks. 109-116
Electronic Edition (link) BibTeX

Eli Biham:
How to decrypt or even substitute DES-encrypted messages in 2²⁸ steps. 117-124
Electronic Edition (link) BibTeX
Seung Mo Cho, Hyung-Ho Kim, Sung Deok Cha, Doo-Hwan Bae:
A semantics of sequence diagrams. 125-130
Electronic Edition (link) BibTeX
Guillaume Fertin, Emmanuel Godard, André Raspaud:
Minimum feedback vertex set and acyclic coloring. 131-139
Electronic Edition (link) BibTeX
Zhi-Zhong Chen, Shiqing Zhang:
Tight upper bound on the number of edges in a bipartite K_{3, 3}-free or K₅-free graph with an application. 141-145
Electronic Edition (link) BibTeX
Hans Kleine Büning, Xishun Zhao:
Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency. 147-151
Electronic Edition (link) BibTeX
Oded Regev:
Priority algorithms for makespan minimization in the subset model. 153-157
Electronic Edition (link) BibTeX
Roberto Baldoni, Giovanna Melideo:
On the minimal information to encode timestamps in distributed computations. 159-166
Electronic Edition (link) BibTeX
Shin-Ichi Nakano:
Efficient generation of plane trees. 167-172
Electronic Edition (link) BibTeX
Tom Araki, Yukio Shibata:
Erratum to "Pancyclicity of recursive circulant graphs": [Information Processing Letters 81 (2002) 187-190]. 173
Electronic Edition (link) BibTeX

Alberto Caprara, Romeo Rizzi:
Packing triangles in bounded degree graphs. 175-180
Electronic Edition (link) BibTeX
Jakub Neumann, Andrzej Szepietowski, Igor Walukiewicz:
Complexity of weak acceptance conditions in tree automata. 181-187
Electronic Edition (link) BibTeX
Kazuhisa Makino, Takashi Takabatake, Satoru Fujishige:
A simple matching algorithm for regular bipartite graphs. 189-193
Electronic Edition (link) BibTeX
Yin-Te Tsai, Yaw-Ling Lin, Fang-Rong Hsu:
The on-line first-fit algorithm for radio frequency assignment problems. 195-199
Electronic Edition (link) BibTeX
Sunil Arya:
Binary space partitions for axis-parallel line segments: Size-height tradeoffs. 201-206
Electronic Edition (link) BibTeX
Enno Ohlebusch:
Hierarchical termination revisited. 207-214
Electronic Edition (link) BibTeX
Samir Khuller, An Zhu:
The General Steiner Tree-Star problem. 215-220
Electronic Edition (link) BibTeX
Minyoung Sung, Soyoung Kim, Sangsoo Park, Naehyuck Chang, Heonshik Shin:
Comparative performance evaluation of Java threads for embedded applications: Linux Thread vs. Green Thread. 221-225
Electronic Edition (link) BibTeX
Rakesh M. Verma:
Algorithms and reductions for rewriting problems II. 227-233
Electronic Edition (link) BibTeX

Oliver Pretzel:
Characterization of simple edge-firing games. 235-236
Electronic Edition (link) BibTeX
Adi Rosén:
A note on models for non-probabilistic analysis of packet switching networks. 237-240
Electronic Edition (link) BibTeX
Stefania Costantini, Ottavio M. D'Antona, Alessandro Provetti:
On the equivalence and range of applicability of graph-based representations of logic programs. 241-249
Electronic Edition (link) BibTeX
Andreas Brandstädt, Suhail Mahfud:
Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. 251-259
Electronic Edition (link) BibTeX
Ken-etsu Fujita:
An interpretation of [lambda][mu]-calculus in [lambda]-calculus. 261-264
Electronic Edition (link) BibTeX
Hung Q. Ngo, Ding-Zhu Du, Ronald L. Graham:
New bounds on a hypercube coloring problem. 265-269
Electronic Edition (link) BibTeX
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan:
More on random walks, electrical networks, and the harmonic k-server algorithm. 271-276
Electronic Edition (link) BibTeX
Hsun-Jung Cho, Li-Yen Hsu:
Ring embedding in faulty honeycomb rectangular torus. 277-284
Electronic Edition (link) BibTeX
Fedor V. Fomin, Dieter Kratsch, Jean-Christophe Novelli:
Approximating minimum cocolorings. 285-290
Electronic Edition (link) BibTeX

Daniel Kirsten:
The finite power problem revisited. 291-294
Electronic Edition (link) BibTeX
Prasanta K. Jana, B. Damodara Naidu, Shailendra Kumar, Manish Arora, Bhabani P. Sinha:
Parallel prefix computation on extended multi-mesh network. 295-303
Electronic Edition (link) BibTeX
Andrea Maggiolo-Schettini, Simone Tini:
On disjunction of literals in triggers of statecharts transitions. 305-310
Electronic Edition (link) BibTeX
Antoni Diller:
Efficient multi-variate abstraction using an array representation for combinators. 311-317
Electronic Edition (link) BibTeX
Carlo Blundo, Stelvio Cimato, Barbara Masucci:
A note on optimal metering schemes. 319-326
Electronic Edition (link) BibTeX
A. L. Rastsvetaev, Lev D. Beklemishev:
On the query complexity of finding a local maximum point. 327-332
Electronic Edition (link) BibTeX
Sean Cleary:
Restricted rotation distance between binary trees. 333-338
Electronic Edition (link) BibTeX
Michael Domaratzki, Giovanni Pighizzini, Jeffrey Shallit:
Simulating finite automata with context-free grammars. 339-344
Electronic Edition (link) BibTeX