Last update:
Fri Oct 20 15:25:20 MDT 2023
Rajesh P. N. Rao and
Jörg Rothe and
Osamu Watanabe Upward separation for ${\rm FewP}$ and
related classes . . . . . . . . . . . . 175--180
Jing Ho Yan and
Gerard J. Chang The path-partition problem in block
graphs . . . . . . . . . . . . . . . . . 317--322
Samir Khuller An $O(|V|^2)$ algorithm for single
connectedness . . . . . . . . . . . . . 105--107
Erkki Mäkinen On inferring linear single-tree
languages . . . . . . . . . . . . . . . 1--3
Eddie Cheng and
Marc J. Lipman On the Day-Tripathi orientation of the
star graphs: Connectivity . . . . . . . 5--10
Jorge Castro and
David Guijarro PACS, simple-PAC and query learning . . 11--16
Michael A. Bender and
Chandra Chekuri Performance guarantees for the TSP with
a parameterized triangle inequality . . 17--21
Mikael Goldmann and
Alexander Russell and
Denis Thérien An ergodic theorem for read-once
non-uniform deterministic finite
automata . . . . . . . . . . . . . . . . 23--28
Michael Saks and
Aravind Srinivasan and
Shiyu Zhou and
David Zuckerman Low discrepancy sets yield approximate
min-wise independent permutation
families . . . . . . . . . . . . . . . . 29--32
Sung Kwon Kim and
Chan-Su Shin and
Tae-Cheon Yang Placing two disks in a convex polygon 33--39
Ted Herman and
Sriram Pemmaraju Error-detecting codes and
fault-containing self-stabilization . . 41--46
Vladimir Pestov On the geometry of similarity search:
Dimensionality curse and concentration
of measure . . . . . . . . . . . . . . . 47--51
Enno Ohlebusch A uniform framework for term and graph
rewriting applied to combined systems 53--59
Giorgio Gambosi and
Gaia Nicosia On-line scheduling with setup costs . . 61--68
Uriel Feige and
Joe Kilian Finding OR in a noisy broadcast network 69--75
Vlady Ravelomanana and
Loÿs Thimonier Patchworks and metablocks enumeration 77--86
Jean Pallo An efficient upper bound of the rotation
distance of binary trees . . . . . . . . 87--92
Shahrokh Saeednia On the security of a convertible group
signature scheme . . . . . . . . . . . . 93--96
Min-Shiang Hwang Cryptanalysis of YCN key assignment
scheme in a hierarchy . . . . . . . . . 97--101
Tzung-Shi Chen Task migration in $2$D wormhole-routed
mesh multicomputers . . . . . . . . . . 103--110
Alberto Caprara and
Hans Kellerer and
Ulrich Pferschy A PTAS for the Multiple Subset Sum
Problem with different knapsack
capacities . . . . . . . . . . . . . . . 111--118
Ferdinando Cicalese and
Ugo Vaccaro An improved heuristic for ``Ulam--Rényi
game'' . . . . . . . . . . . . . . . . . 119--124
Rolf Niedermeier and
Peter Rossmanith A general method to speed up
fixed-parameter-tractable algorithms . . 125--129
Guillaume Fertin Hierarchical broadcast and gossip
networks . . . . . . . . . . . . . . . . 131--136
David Avis and
Luc Devroye Estimating the number of vertices of a
polyhedron . . . . . . . . . . . . . . . 137--143
Sukumar Ghosh and
Xin He Fault-containing self-stabilization
using priority scheduling . . . . . . . 145--151
Andrzej Ehrenfeucht and
Jurriaan Hage and
Tero Harju and
Grzegorz Rozenberg Pancyclicity in switching classes . . . 153--156
Raymond Devillers and
Joël Goossens Liu and Layland's schedulability test
revisited . . . . . . . . . . . . . . . 157--161
Atsushi Kaneko and
Kiyoshi Yoshimoto On spanning trees with restricted
degrees . . . . . . . . . . . . . . . . 163--165
Liang Chen and
Naoyuki Tokuda A note on ``Category and measure in
complexity classes'' . . . . . . . . . . 167--168
Steven McKellar and
Robert Davis Redundancy removal in multicast
protocols . . . . . . . . . . . . . . . 169--173
Zoltán Fülöp and
Sebastian Maneth Domains of partial attributed tree
transducers . . . . . . . . . . . . . . 175--180
Fanica Gavril Maximum weight independent sets and
cliques in intersection graphs of
filaments . . . . . . . . . . . . . . . 181--188
G. Dimauro and
S. Impedovo and
G. Pirlo and
A. Salzo RNS architectures for the implementation
of the `diagonal function' . . . . . . . 189--198
A. Nayak and
J. Ren and
N. Santoro An improved testing scheme for
catastrophic fault patterns . . . . . . 199--206
Achour Mostefaoui and
Michel Raynal and
Frédéric Tronel From Binary Consensus to Multivalued
Consensus in asynchronous
message-passing systems . . . . . . . . 207--212
Amos Beimel and
Eyal Kushilevitz Learning unions of high-dimensional
boxes over the reals . . . . . . . . . . 213--220
Daniel \vStefankovi\vc Acyclic orientations do not lead to
optimal deadlock-free packet routing
algorithms . . . . . . . . . . . . . . . 221--225
Anonymous Index . . . . . . . . . . . . . . . . . 227--228
Anonymous Index . . . . . . . . . . . . . . . . . 229--230
Johan Håstad On bounded occurrence constraint
satisfaction . . . . . . . . . . . . . . 1--6
François Bertault A force-directed algorithm that
preserves edge-crossing properties . . . 7--13
Manfred Göbel Rings of polynomial invariants of the
alternating group have no finite SAGBI
bases with respect to any admissible
order . . . . . . . . . . . . . . . . . 15--18
Alok Baveja and
Aravind Srinivasan Approximating low-congestion routing and
column-restricted packing problems . . . 19--25
Jean-Marc Talbot The $\exists\forall^2$ fragment of the
first-order theory of atomic set
constraints is $\Pi^0_1$-hard . . . . . 27--33
Joachim Niehren and
Sophie Tison and
Ralf Treinen On rewrite constraints and context
unification . . . . . . . . . . . . . . 35--40
Arnold Schönhage Variations on computing reciprocals of
power series . . . . . . . . . . . . . . 41--46
Margus Veanes Farmer's Theorem revisited . . . . . . . 47--53
Carlos H. C. Duarte and
Tom Maibaum A rely-guarantee discipline for open
distributed systems design . . . . . . . 55--63
Theodosis Dimitrakos and
Tom Maibaum On a generalized modularization theorem 65--71
Wolfgang W. Bein and
Lawrence L. Larmore Trackless online algorithms for the
server problem . . . . . . . . . . . . . 73--79
Antoine Vigneron and
Lixin Gao and
Mordecai J. Golin and
Giuseppe F. Italiano and
Bo Li An algorithm for finding a $k$-median in
a directed tree . . . . . . . . . . . . 81--88
Rajesh P. N. Rao and
Jörg Rothe and
Osamu Watanabe Corrigendum to ``Upward separation for
FewP and related classes'', Information
Processing Letters \bf 52(4) (1994)
175--180 . . . . . . . . . . . . . . . . 89--89
Ingo Wegener Worst case examples for operations on
OBDDs . . . . . . . . . . . . . . . . . 91--96
Sarnath Ramnath and
Peiyi Zhao On the isomorphism of expressions . . . 97--102
Kuo-Liang Chung On finding medians of weighted discrete
points . . . . . . . . . . . . . . . . . 103--106
Harold N. Gabow Path-based depth-first search for strong
and biconnected components . . . . . . . 107--114
Ton Kloks and
Dieter Kratsch and
Haiko Müller Finding and counting small induced
subgraphs efficiently . . . . . . . . . 115--121
Satoru Iwata and
S. Thomas McCormick and
Maiko Shigeno A fast cost scaling algorithm for
submodular flow . . . . . . . . . . . . 123--128
Stavros D. Nikolopoulos Recognizing cographs and threshold
graphs through a classification of their
edges . . . . . . . . . . . . . . . . . 129--139
Laurent Granvilliers and
Gaétan Hains A conservative scheme for parallel
interval narrowing . . . . . . . . . . . 141--146
Agostino Dovier and
Enrico Pontelli and
Gianfranco Rossi A necessary condition for Constructive
Negation in Constraint Logic Programming 147--156
Dimitris J. Kavvadias and
Martha Sideri and
Elias C. Stavropoulos Generating all maximal models of a
Boolean expression . . . . . . . . . . . 157--162
Joseph Kee-Yin Ng and
Shibin Song and
Wei Zhao Statistical delay analysis on an ATM
switch with self-similar input traffic 163--173
Markus Schneider On distribution properties of sequences
with perfect linear complexity profile 175--182
Cao An Wang and
Francis Y. Chin and
Boting Yang Triangulations without minimum-weight
drawing . . . . . . . . . . . . . . . . 183--189
Palash Sarkar A note on the spectral characterization
of correlation immune Boolean functions 191--195
Pavel Pudlák A note on the use of determinant for
proving lower bounds on the size of
linear circuits . . . . . . . . . . . . 197--201
Jérôme Durand-Lose Randomized uniform self-stabilizing
mutual exclusion . . . . . . . . . . . . 203--207
Jae Dong Yang A concept-based query evaluation with
indefinite fuzzy triples . . . . . . . . 209--214
Sukhamay Kundu An optimal $O(N^2)$ algorithm for
computing the min-transitive closure of
a weighted graph . . . . . . . . . . . . 215--220
Ahmed Bouajjani and
Javier Esparza and
Alain Finkel and
Oded Maler and
Peter Rossmanith and
Bernard Willems and
Pierre Wolper An efficient automata approach to some
problems on context-free grammars . . . 221--227
Weimin Chen Multi-subsequence searching . . . . . . 229--233
Byoung-Mo Im and
Myoung Ho Kim and
Hyung-Il Kang and
Jae Soo Yoo Declustering signature files based on a
dynamic measure . . . . . . . . . . . . 235--241
Alfredo De Santis and
Barbara Masucci On secret set schemes . . . . . . . . . 243--251
Gautam Das and
Michiel Smid A lower bound for approximating the
geometric minimum weight matching . . . 253--255
Jenn-Wei Lin and
Sy-Yen Kuo Resolving error propagation in
distributed systems . . . . . . . . . . 257--262
Samir Khuller Addendum to ``An $O(|V|^2)$ algorithm
for single connectedness'', [Information
Processing Letters 72(3--4) (1999)
105--107] . . . . . . . . . . . . . . . 263--263
Anonymous Index . . . . . . . . . . . . . . . . . 265--266
Anonymous Index . . . . . . . . . . . . . . . . . 267--268
Béatrice Bérard and
Catherine Dufourd Timed automata and additive clock
constraints . . . . . . . . . . . . . . 1--7
Charles J. Colbourn and
Alan C. H. Ling Quorums from difference covers . . . . . 9--12
Mayer Goldberg Gödelization in the lambda calculus . . . 13--16
Jacob M. Howe and
Andy King Abstracting numeric constraints with
Boolean functions . . . . . . . . . . . 17--23
Meghanad D. Wagh and
Prakash Math and
Osman Guzide Cyclic-cubes and wrap-around butterflies 25--27
Michal Penn and
Moshe Tennenholtz Constrained multi-object auctions and
$b$-matching . . . . . . . . . . . . . . 29--34
Ju-Hong Lee and
Deok-Hwan Kim and
Seok-Lyong Lee and
Chin-Wan Chung and
Guang-Ho Cha Distributed similarity search algorithm
in distributed heterogeneous multimedia
databases . . . . . . . . . . . . . . . 35--42
Ari Freund and
Howard Karloff A lower bound of $8/(7+\frac{1}{k-1})$
on the integrality ratio of the
C\ualinescu-Karloff-Rabani relaxation
for multiway cut . . . . . . . . . . . . 43--50
A. B. Premkumar On the optimal utilization of all
available states in the $2^n$ moduli set 51--56
Gerth Stòlting Brodal and
S. Venkatesh Improved bounds for dictionary look-up
with one error . . . . . . . . . . . . . 57--59
Keh-Ning Chang and
Shi-Chun Tsai Exact solution of a minimal recurrence 61--64
Krzysztof Giaro and
Marek Kubale Edge-chromatic sum of trees and bounded
cyclicity graphs . . . . . . . . . . . . 65--69
Toru Hasunuma On edge-disjoint spanning trees with
small depths . . . . . . . . . . . . . . 71--74
Marek Chrobak and
Ji\vrí Sgall A simple analysis of the harmonic
algorithm for two servers . . . . . . . 75--77
Yaoyun Shi Lower bounds of quantum black-box
complexity and degree of approximating
polynomials by influence of Boolean
variables . . . . . . . . . . . . . . . 79--83
Poul Frederick Williams and
Macha Nikolska\"\ia and
Antoine Rauzy Bypassing BDD construction for
reliability analysis . . . . . . . . . . 85--89
Ulrich Hertrampf and
Steffen Reith and
Heribert Vollmer A note on closure properties of logspace
MOD classes . . . . . . . . . . . . . . 91--93
Sergei Bespamyatnikh and
Michael Segal Covering a set of points by two
axis-parallel boxes . . . . . . . . . . 95--100
P. Oscar Boykin and
Tal Mor and
Matthew Pulver and
Vwani Roychowdhury and
Farrokh Vatan A new universal and fault-tolerant
quantum basis . . . . . . . . . . . . . 101--107
Andris Ambainis How rich is the structure of the
intrinsic complexity of learning . . . . 109--112
D. J. Guan and
Chun-Yen Chou and
Chiou-Wei Chen Computational complexity of similarity
retrieval in a pictorial database . . . 113--117
Wolfgang Günther and
Rolf Drechsler On the computational power of linearly
transformed BDDs . . . . . . . . . . . . 119--125
Massimiliano Goldwurm and
Massimo Santini Clique polynomials have a unique root of
smallest modulus . . . . . . . . . . . . 127--132
Hans-Joachim Böckenhauer and
Juraj Hromkovi\vc and
Ralf Klasing and
Sebastian Seibert and
Walter Unger Approximation algorithms for the TSP
with sharpened triangle inequality . . . 133--138
Peter Hòyer Simplified proof of the Fourier Sampling
Theorem . . . . . . . . . . . . . . . . 139--143
K. V. R. C. N. Kishore and
Sanjeev Saxena An optimal parallel algorithm for
general maximal matchings is as easy as
for bipartite graphs . . . . . . . . . . 145--151
Bor-Kuan Lu and
Fang-Rong Hsu and
Chuan Yi Tang Guarding in a simple polygon . . . . . . 153--158
Fang-Cheng Leu and
Yin-Te Tsai and
Chuan Yi Tang An efficient external sorting algorithm 159--163
Ion I. M\uandoiu and
Alexander Z. Zelikovsky A note on the MST heuristic for bounded
edge-length Steiner trees with minimum
number of Steiner points . . . . . . . . 165--167
Alon Efrat and
Matthew J. Katz Computing Euclidean bottleneck matchings
in higher dimensions . . . . . . . . . . 169--174
Paolo Boldi and
Sebastiano Vigna Coverings that preserve sense of
direction . . . . . . . . . . . . . . . 175--180
Refael Hassin and
Shlomi Rubinstein Better approximations for max TSP . . . 181--186
Zichen Li and
L. C. K. Hui and
K. P. Chow and
C. F. Chong and
W. W. Tsang and
H. W. Chan Security of Tseng--Jan's group signature
schemes . . . . . . . . . . . . . . . . 187--189
Eric Gamess plapackJava: Towards an efficient Java
interface for high performance parallel
linear algebra . . . . . . . . . . . . . 191--197
S. Zeadally Performance evaluation of a Java-based
networking Application Programming
Interface (API) . . . . . . . . . . . . 199--209
Andreu Riera and
Josep Rif\`a and
Joan Borrell Efficient construction of vote-tags to
allow open objection to the tally in
electronic elections . . . . . . . . . . 211--215
John Ellis and
Tobias Krahn and
Hongbing Fan Computing the cycles in the perfect
shuffle permutation . . . . . . . . . . 217--224
Bang Ye Wu Polynomial time algorithms for some
minimum latency problems . . . . . . . . 225--229
F. K. Hwang and
C. K. Pai Sequential construction of a circular
consecutive-$2$ system . . . . . . . . . 231--235
T. Tambouratzis Solving the Hamiltonian cycle problem
via an artificial neural network . . . . 237--242
Daisuke Takahashi A fast algorithm for computing large
Fibonacci numbers . . . . . . . . . . . 243--246
Ing-Ray Chen and
Ding-Chau Wang and
Chih-Ping Chu Response time behavior of distributed
voting algorithms for managing
replicated data . . . . . . . . . . . . 247--253
Carlo Blundo and
Alfredo De Santis and
Moni Naor Visual cryptography for grey level
images . . . . . . . . . . . . . . . . . 255--259
Kousha Etessami A note on a question of Peled and Wilke
regarding stutter-invariant LTL . . . . 261--263
Stavros D. Nikolopoulos and
Charis Papadopoulos On the performance of the first-fit
coloring algorithm on permutation graphs 265--273
Claus Rick Simple and fast linear space computation
of longest common subsequences . . . . . 275--281
Anonymous Index . . . . . . . . . . . . . . . . . 283--284
Anonymous Index . . . . . . . . . . . . . . . . . 285--286
Riccardo Focardi and
Flaminia L. Luccio and
David Peleg Feedback vertex set in hypercubes . . . 1--5
Sergei Bespamyatnikh and
Michael Segal Enumerating longest increasing
subsequences and patience sorting . . . 7--11
Ryuhei Uehara and
Zhi-Zhong Chen Parallel approximation algorithms for
maximum weighted matching in general
graphs . . . . . . . . . . . . . . . . . 13--17
Tomasz Borzyszkowski Generalized interpolation in C ASL . . . 19--24
Lanfranco Lopriore Protection in a single-address-space
environment . . . . . . . . . . . . . . 25--32
Matthias Schonlau and
Martin Theus Detecting masquerades in intrusion
detection based on unpopular commands 33--38
Joan Serra-Sagrist\`a Enumeration of lattice points in $l_1$
norm . . . . . . . . . . . . . . . . . . 39--44
Jue Xue and
Ju Liu A network-flow-based lower bound for the
minimum weighted integer coloring
problem . . . . . . . . . . . . . . . . 45--50
Joep Aerts and
Jan Korst and
Sebastian Egner Random duplicate storage strategies for
load balancing in multimedia servers . . 51--59
Jin-Yi Cai and
Ajay Nerurkar A note on the non-NP-hardness of
approximate lattice problems under
general Cook reductions . . . . . . . . 61--66
L. J. García-Villalba and
A. Fúster-Sabater On the linear complexity of the
sequences generated by nonlinear
filterings . . . . . . . . . . . . . . . 67--73
Chu Min Li Equivalency reasoning to solve a class
of hard SAT problems . . . . . . . . . . 75--81
Francesc Comellas and
Javier Ozón and
Joseph G. Peters Deterministic small-world communication
networks . . . . . . . . . . . . . . . . 83--90
Stefan Dobrev and
Heiko Schröder and
Ondrej Sýkora and
Imrich Vrt'o Evolutionary graph colouring . . . . . . 91--94
Igor E. Shparlinski Linear complexity of the Naor--Reingold
pseudo-random function . . . . . . . . . 95--99
Akira Higuchi and
Naofumi Takagi A fast addition algorithm for elliptic
curve arithmetic in ${\rm GF}(2n)$ using
projective coordinates . . . . . . . . . 101--103
Keon-Jik Lee and
Kee-Young Yoo Linear systolic multiplier/squarer for
fast exponentiation . . . . . . . . . . 105--111
Kuo-Liang Chung and
Wen-Ming Yan On the number of spanning trees of a
multi-complete/star related graph . . . 113--119
Ho-Hyun Park and
Chin-Wan Chung Complexity of estimating multi-way join
result sizes for area skewed spatial
data . . . . . . . . . . . . . . . . . . 121--129
Leslie Lamport and
Sharon Perl and
William Weihl When does a correct mutual exclusion
algorithm guarantee mutual exclusion? 131--134
Hyun-Sung Kim and
Sung-Woo Lee and
Kee-Young Yoo Partitioned systolic architecture for
modular multiplication in GF (2 m ) 135--139
F. Roussel and
I. Rusu Recognizing $i$-triangulated graphs in
$O(mn)$ time . . . . . . . . . . . . . . 141--147
Leah Epstein A note on on-line scheduling with
precedence constraints on identical
machines . . . . . . . . . . . . . . . . 149--153
Wolfgang W. Bein and
Rudolf Fleischer and
Lawrence L. Larmore Limited bookmark randomized online
algorithms for the paging problem . . . 155--162
Xuehou Tan On optimal bridges between two convex
regions . . . . . . . . . . . . . . . . 163--168
Limin Xiang and
Kazuo Ushijima and
Changjie Tang Efficient loopless generation of Gray
codes for $k$-ary trees . . . . . . . . 169--174
Erez Hartuv and
Ron Shamir A clustering algorithm based on graph
connectivity . . . . . . . . . . . . . . 175--181
Anonymous Index . . . . . . . . . . . . . . . . . 183--184
Anonymous Index . . . . . . . . . . . . . . . . . 185--186
Anonymous Index . . . . . . . . . . . . . . . . . 187--290
Clemens Gröpl and
Hans Jürgen Prömel and
Anand Srivastav On the evolution of the worst-case OBDD
size . . . . . . . . . . . . . . . . . . 1--7
Andris Ambainis On learning formulas in the limit and
with assurance . . . . . . . . . . . . . 9--11
Esther M. Arkin and
Refael Hassin and
Maxim Sviridenko Approximating the maximum quadratic
assignment problem . . . . . . . . . . . 13--16
Shyue-Ming Tang and
Fu-Long Yeh and
Yue-Li Wang An efficient algorithm for solving the
homogeneous set sandwich problem . . . . 17--22
Xuehou Tan Shortest zookeeper's routes in simple
polygons . . . . . . . . . . . . . . . . 23--26
Xuehou Tan Fast computation of shortest watchman
routes in simple polygons . . . . . . . 27--33
Tseng-Kuei Li and
Jimmy J. M. Tan and
Lih-Hsing Hsu and
Ting-Yi Sung The shuffle-cubes and their
generalization . . . . . . . . . . . . . 35--41
Jean-Marie Le Bars The $0$-$1$ law fails for monadic
existential second-order logic on
undirected graphs . . . . . . . . . . . 43--48
Vicki L. Almstrum and
David Gries From the Editors of this special issue 49--51
Edsger W. Dijkstra Under the spell of Leibniz's dream . . . 53--61
James H. Anderson and
Mark Moir and
Srikanth Ramamurthy A simple proof technique for
priority-scheduled systems . . . . . . . 63--70
Roland Backhouse and
Maarten Fokkinga The associativity of equivalence and the
Towers of Hanoi problem . . . . . . . . 71--76
Lex Bijlsma Model-based specification . . . . . . . 77--84
D. W. Braben Bucking the trends . . . . . . . . . . . 85--87
W. H. J. Feijen The joy of formula manipulation . . . . 89--96
Cormac Flanagan and
Rajeev Joshi and
K. Rustan M. Leino Annotation inference for modular
checkers . . . . . . . . . . . . . . . . 97--108
Mohamed G. Gouda Elements of security: Closure,
convergence, and protection . . . . . . 109--114
Ted Herman and
Toshimitsu Masuzawa Available stabilizing heaps . . . . . . 115--121
Tony Hoare Legacy . . . . . . . . . . . . . . . . . 123--129
H. Peter Hofstee and
Jun Sawada Derivation of a rotator circuit with
homogeneous interconnect . . . . . . . . 131--135
Rob R. Hoogerwoord Formality works . . . . . . . . . . . . 137--142
Jerry James and
Ambuj K. Singh Recovering distributed objects . . . . . 143--150
Anne Kaldewaij and
Laurens de Vries Optimal real-time garbage collection for
acyclic pointer structures . . . . . . . 151--157
William Leal and
Anish Arora State-level and value-level simulations
in data refinement . . . . . . . . . . . 159--167
K. Rustan M. Leino Real estate of names . . . . . . . . . . 169--171
Panagiotis Manolios and
J. Strother Moore On the desirability of mechanizing
calculational proofs . . . . . . . . . . 173--179
Alain J. Martin Towards an energy complexity of
computation . . . . . . . . . . . . . . 181--187
M. Douglas McIlroy The music of streams . . . . . . . . . . 189--195
Jayadev Misra A walk over the shortest path:
Dijkstra's Algorithm viewed as
fixed-point computation . . . . . . . . 197--200
David A. Naumann Calculating sharp adaptation rules . . . 201--208
Josyula R. Rao On the role of formal methods in
security . . . . . . . . . . . . . . . . 209--212
Beverly A. Sanders The shortest path in parallel . . . . . 213--217
Xuandong Li and
Johan Lilius Efficient verification of a class of
time Petri nets using linear programming 219--224
Gerhard J. Woeginger The reconstruction of polyominoes from
their orthogonal projections . . . . . . 225--229
Limin Xiang and
Kazuo Ushijima and
Changjie Tang On generating $k$-ary trees in computer
representation . . . . . . . . . . . . . 231--238
Carlos Martín-Vide and
Victor Mitrana Some undecidable problems for parallel
communicating finite automata systems 239--245
Paulo A. S. Veloso and
Sheila R. M. Veloso On local modularity variants and
$\Pi$-institutions . . . . . . . . . . . 247--253
Michelangelo Grigni A Sperner lemma complete for PPA . . . . 255--259
Chinda Wongngamnit and
Dana Angluin Robot localization in a grid . . . . . . 261--267
Hiroyuki Kawai and
Naohiro Fujikake and
Yukio Shibata Factorization of de Bruijn digraphs by
cycle-rooted trees . . . . . . . . . . . 269--275
Frank Harary and
Vladik Kreinovich and
Luc Longpré A new graph characteristic and its
application to numerical computability 277--282
Vicent Cholvi and
Pablo Boronat A minimal property for characterizing
deadlock-free programs . . . . . . . . . 283--290
Anonymous Subject Index --- Volume 77 (2001) . . . 291--292
Anonymous Author Index --- Volume 77 (2001) . . . 293--294
Anonymous Preface . . . . . . . . . . . . . . . . 1--3
Anonymous Subject Index to Volumes 1--75 . . . . . 5--336
Anonymous Reference List of Indexed Articles . . . 337--448
Kuo-Liang Chung and
Wen-Ming Yan An efficient algorithm for the Fourier
transform on a compressed image in
restricted quadtree and shading format 1--5
Ferucio Lauren\ctiu \cTiplea and
Erkki Mäkinen A note on synchronized extension systems 7--9
Yu-Wei Chen and
Kuo-Liang Chung Fault-tolerant algorithm for Fast
Fourier Transform on hypercubes . . . . 11--16
A. Agnetis and
P. Detti and
C. Meloni and
D. Pacciarelli A linear algorithm for the Hamiltonian
completion number of the line graph of a
tree . . . . . . . . . . . . . . . . . . 17--24
Gautam B. Singh and
Donglin Liu Sequence retrieval from genomic
databases . . . . . . . . . . . . . . . 25--32
Eric C. R. Hehner Variables and scopes considered formally 33--38
N. C. Audsley On priority assignment in fixed priority
scheduling . . . . . . . . . . . . . . . 39--44
Franz Wotawa A variant of Reiter's hitting-set
algorithm . . . . . . . . . . . . . . . 45--51
Gianluca De Marco and
Andrzej Pelc Faster broadcasting in unknown radio
networks . . . . . . . . . . . . . . . . 53--56
J. Burghardt and
F. Kammüller and
J. W. Sanders On the antisymmetry of Galois embeddings 57--63
Kalim Qureshi and
Masahiko Hatanaka A practical approach of task scheduling
and load balancing on heterogeneous
distributed raytracing systems . . . . . 65--71
Kien-Weh Chin and
Hsu-Chun Yen The symmetry number problem for trees 73--79
Enrico Nardelli and
Guido Proietti and
Peter Widmayer A faster computation of the most vital
edge of a shortest path . . . . . . . . 81--85
Catherine McCartin An improved algorithm for the jump
number problem . . . . . . . . . . . . . 87--92
C. P. Schnorr Small generic hardcore subsets for the
discrete logarithm: Short secret DL-keys 93--98
Rachid Guerraoui On the hardness of failure-sensitive
agreement problems . . . . . . . . . . . 99--104
Christof Löding Efficient minimization of deterministic
weak omega-automata . . . . . . . . . . 105--109
Jan Van den Bussche Rewriting queries using views over
monadic database schemas . . . . . . . . 111--114
Xuehou Tan Optimal computation of the Voronoi
diagram of disjoint clusters . . . . . . 115--119
Friedrich Eisenbrand Short vectors of planar lattices via
continued fractions . . . . . . . . . . 121--126
Kil-Hyun Jeong and
Jong-Kyu Lee and
Hee-Kuck Oh Performance analysis of a multicasting
protocol with contention-less minislots 127--133
Lusheng Chen and
Fang-Wei Fu and
Victor K.-W. Wei On the constructions of highly nonlinear
zigzag functions and unbiased functions 135--140
Stavros Cosmadakis and
Gabriel Kuper and
Leonid Libkin On the orthographic dimension of
definable sets . . . . . . . . . . . . . 141--145
József Békési and
Gábor Galambos Worst-case analysis of the Iterated
Longest Fragment algorithm . . . . . . . 147--153
Piotr Chrz\castowski-Wachtel and
Jerzy Tyszkiewicz and
Achim Hoffmann and
Arthur Ramer Definability of connectives in
conditional event algebras of
Schay-Adams-Calabrese and
Goodman-Nguyen-Walker . . . . . . . . . 155--160
Jaap-Henk Hoepman Can an operation both update the state
and return a meaningful value in the
asynchronous PRAM model? . . . . . . . . 161--166
Pantelimon St\uanic\uaand Soo Hak Sung Improving the nonlinearity of certain
balanced Boolean functions with good
local and global avalanche
characteristics . . . . . . . . . . . . 167--172
E. Knill and
R. Laflamme Quantum computing and quadratically
signed weight enumerators . . . . . . . 173--179
Uriel Feige and
Marek Karpinski and
Michael Langberg A note on approximating Max-Bisection on
regular graphs . . . . . . . . . . . . . 181--188
Valmir C. Barbosa and
Mario R. F. Benevides and
Ayru L. Oliveira Filho A priority dynamics for generalized
drinking philosophers . . . . . . . . . 189--195
Graham Hutton and
Jeremy Gibbons The generic approximation lemma . . . . 197--201
Robert Fidytek and
Andrzej W. Mostowski and
Rafa\l Somla and
Andrzej Szepietowski Algorithms counting monotone Boolean
functions . . . . . . . . . . . . . . . 203--209
Ilya Shmulevich and
Aleksey D. Korshunov and
Jaakko Astola Almost all monotone Boolean functions
are polynomially learnable using
membership queries . . . . . . . . . . . 211--213
Binay Bhattacharya and
Robert Benkoczi On computing the optimal bridge between
two convex polygons . . . . . . . . . . 215--221
Bronislava Brejová Analyzing variants of Shellsort . . . . 223--227
D. P. Wang An optimal algorithm for constructing an
optimal bridge between two simple
rectilinear polygons . . . . . . . . . . 229--236
Adrian Dumitrescu and
William Steiger Space-time trade-offs for some ranking
and searching queries . . . . . . . . . 237--241
Rahul Santhanam Lower bounds on the complexity of
recognizing SAT by Turing machines . . . 243--247
Alex de V. Garcia and
Edward Hermann Haeusler Code migration and program
maintainability --- A categorical
perspective . . . . . . . . . . . . . . 249--254
P. Bonizzoni and
C. Ferretti and
G. Mauri and
R. Zizza Separating some splicing models . . . . 255--259
P. Bonizzoni and
C. Ferretti and
G. Mauri and
R. Zizza Separating some splicing models . . . . 255--259
Toshihiro Fujito On approximability of the
independent/connected edge dominating
set problems . . . . . . . . . . . . . . 261--266
Toshihiro Fujito On approximability of the
independent/connected edge dominating
set problems . . . . . . . . . . . . . . 261--266
Rocco A. Servedio On the limits of efficient teachability 267--272
Rocco A. Servedio On the limits of efficient teachability 267--272
Guohua Wan and
Benjamin P.-C. Yen and
Chung-Lun Li Single machine scheduling to minimize
total compression plus weighted flow
cost is NP-hard . . . . . . . . . . . . 273--280
Guohua Wan and
Benjamin P.-C. Yen and
Chung-Lun Li Single machine scheduling to minimize
total compression plus weighted flow
cost is NP-hard . . . . . . . . . . . . 273--280
Wendy Myrvold and
Frank Ruskey Ranking and unranking permutations in
linear time . . . . . . . . . . . . . . 281--284
Wendy Myrvold and
Frank Ruskey Ranking and unranking permutations in
linear time . . . . . . . . . . . . . . 281--284
Sachin B. Patkar and
H. Narayanan A note on optimal covering augmentation
for graphic polymatroids . . . . . . . . 285--290
Sachin B. Patkar and
H. Narayanan A note on optimal covering augmentation
for graphic polymatroids . . . . . . . . 285--290
Svetlana A. Kravchenko and
Frank Werner A heuristic algorithm for minimizing
mean flow time with unit setups . . . . 291--296
Svetlana A. Kravchenko and
Frank Werner A heuristic algorithm for minimizing
mean flow time with unit setups . . . . 291--296
Jie Wu and
Li Sheng An efficient sorting algorithm for a
sequence of kings in a tournament . . . 297--299
Jie Wu and
Li Sheng An efficient sorting algorithm for a
sequence of kings in a tournament . . . 297--299
Anonymous Subject Index --- Volume 79 . . . . . . 301--302
Anonymous Subject Index --- Volume 79 . . . . . . 301--302
Anonymous Author Index --- Volume 79 . . . . . . . 303--304
Luca Aceto and
Wan Fokkink Preface . . . . . . . . . . . . . . . . 1
Anna Philippou and
Oleg Sokolsky and
Insup Lee and
Rance Cleaveland and
Scott A. Smolka Hiding resources that can fail: An
axiomatic perspective . . . . . . . . . 3--13
D. Cazorla and
F. Cuartero and
V. Valero and
F. L. Pelayo A process algebra for probabilistic and
nondeterministic processes . . . . . . . 15--23
Corrado Priami and
Aviv Regev and
Ehud Shapiro and
William Silverman Application of a stochastic name-passing
calculus to representation and
simulation of molecular processes . . . 25--31
Mark B. van der Zwaag The cones and foci proof technique for
timed transition systems . . . . . . . . 33--40
Jan A. Bergstra and
Alban Ponse Process algebra and conditional
composition . . . . . . . . . . . . . . 41--49
Marc Voorhoeve and
Sjouke Mauw Impossible futures and determinism . . . 51--58
Alban Ponse and
Yaroslav S. Usenko Equivalence of recursive specifications
in process algebra . . . . . . . . . . . 59--65
Jovan Dj. Goli\'c A probabilistic cryptanalytic method for
a time-variant permutation generator . . 67--73
H. Sarbazi-Azad and
M. Ould-Khaoua and
L. M. Mackenzie Algorithmic construction of Hamiltonians
in pyramids . . . . . . . . . . . . . . 75--79
Jorge Alberto Calvo and
Danny Krizanc and
Pat Morin and
Michael Soss and
Godfried Toussaint Convexifying polygons with simple
projections . . . . . . . . . . . . . . 81--86
Seok-Lyong Lee and
Chin-Wan Chung On the effective clustering of
multidimensional data sequences . . . . 87--95
Sanjoy Baruah Scheduling periodic tasks on uniform
multiprocessors . . . . . . . . . . . . 97--104
Roberto Baldoni and
Jean-Michel Hélary and
Achour Mostéfaoui and
Michel Raynal Impossibility of scalar clock-based
communication-induced checkpointing
protocols ensuring the RDT property . . 105--111
Hung-Yu Chien and
Tzong-Chen Wu and
Jinn-Ke Jan and
Yuh-Min Tseng Cryptanalysis of Chang--Wu's
group-oriented authentication and key
exchange protocols . . . . . . . . . . . 113--117
G. Costagliola and
V. Deufemia and
F. Ferrucci and
C. Gravino Decidability of the consistency problem
for regular symbolic picture description
languages . . . . . . . . . . . . . . . 119--124
E. Bertsch and
M.-J. Nederhof Size/lookahead tradeoff for
LL($k$)-grammars . . . . . . . . . . . . 125--129
Flemming Nielson and
Hanne Riis Nielson and
Mooly Sagiv Kleene's Logic with Equality . . . . . . 131--137
Ahmad Kadrie and
V. R. Dare and
D. G. Thomas and
K. G. Subramanian Algebraic properties of the shuffle over
$\omega$-trajectories . . . . . . . . . 139--144
Franck Seynhaeve Set constraints and topology . . . . . . 145--150
Saâd Biaz and
Jennifer L. Welch Closed form bounds for clock
synchronization under simple uncertainty
assumptions . . . . . . . . . . . . . . 151--157
Shing-Tsaan Huang and
Bau-Wen Chen Optimal $1$-fair alternators . . . . . . 159--163
Mathieu Raffinot On maximal repeats in strings . . . . . 165--169
Refael Hassin and
Shlomi Rubinstein Approximation algorithms for maximum
linear arrangement . . . . . . . . . . . 171--177
Jérôme Monnot The maximum f-depth spanning tree
problem . . . . . . . . . . . . . . . . 179--187
Minkyu Lee and
Dongsoo Han and
Jaeyong Shim Set-based access conflict analysis of
concurrent workflow definition . . . . . 189--194
Dong-Joo Park and
Shin Heu and
Hyoung-Joo Kim The RS-tree: An efficient data structure
for distance browsing queries . . . . . 195--203
Ye-In Chang and
Bor-Hsu Chen A generalized grid quorum strategy for
$k$-mutual exclusion in distributed
systems . . . . . . . . . . . . . . . . 205--212
Goran Konjevod and
R. Ravi and
F. Sibel Salman On approximating planar metrics by tree
metrics . . . . . . . . . . . . . . . . 213--219
Stephen T. Hedetniemi and
David P. Jacobs and
Pradip K. Srimani Maximal matching stabilizes in time
$O(m)$ . . . . . . . . . . . . . . . . . 221--223
Han Wook Lee and
Dae Woong Kim and
Chan-Ik Park Phased RGSS: An improved disk array
scheduling for continuous media
retrieval . . . . . . . . . . . . . . . 225--231
Clare Martin and
Jeremy Gibbons On the semantics of nested datatypes . . 233--238
María Isabel González Vasco and
Rainer Steinwandt Clouds over a public key cryptosystem
based on Lyndon words . . . . . . . . . 239--242
Jaikumar Radhakrishnan and
Venkatesh Raman A tradeoff between search and update in
dictionaries . . . . . . . . . . . . . . 243--247
Christos Nomikos and
Aris Pagourtzis and
Stathis Zachos Routing and path multicoloring . . . . . 249--256
Frederic Green and
Randall Pruim Relativized separation of EQP from
P$^{\mbox{NP}}$ . . . . . . . . . . . . 257--260
N. P. Smart A note on the $x$-coordinate of points
on an elliptic curve in characteristic
two . . . . . . . . . . . . . . . . . . 261--263
Xudong Guan and
Yiling Yang and
Jinyuan You Typing evolving ambients . . . . . . . . 265--270
Justin Zobel and
Steffen Heinz and
Hugh E. Williams In-memory hash tables for accumulating
text vocabularies . . . . . . . . . . . 271--277
Maxime Crochemore and
Costas S. Iliopoulos and
Yoan J. Pinzon and
James F. Reid A fast and practical bit-vector
algorithm for the Longest Common
Subsequence problem . . . . . . . . . . 279--285
Hiroshi Nagamochi and
Toshimasa Ishii and
Hiro Ito Minimum cost source location problem
with vertex-connectivity requirements in
digraphs . . . . . . . . . . . . . . . . 287--293
Z. C. Li and
L. C. K. Hui and
K. P. Chow and
C. F. Chong and
W. W. Tsang and
H. W. Chan Security of Wang et al.'s group-oriented
$(t,n)$ threshold signature schemes with
traceable signers . . . . . . . . . . . 295--298
Erl-Huei Lu and
Shao-Wei Wu and
Yi-Chang Cheng A decoding algorithm for
triple-error-correcting binary BCH codes 299--303
Guoqing Wang and
T. C. Edwin Cheng Heuristics for two-machine no-wait
flowshop scheduling with an availability
constraint . . . . . . . . . . . . . . . 305--309
Laurence Boxer and
Russ Miller A parallel algorithm for approximate
regularity . . . . . . . . . . . . . . . 311--316
Anonymous Subject Index --- Volume 80 (2001) . . . 317--318
Anonymous Author Index --- Volume 80 (2001) . . . 319--321
Anonymous Master Subject Index --- Volumes 71--80 323--331
Anonymous Master Index---Volumes 71--80 . . . . . 333--342
Michael Krivelevich Deciding $k$-colorability in expected
polynomial time . . . . . . . . . . . . 1--6
V. V. Lozin On maximum induced matchings in
bipartite graphs . . . . . . . . . . . . 7--11
Kuo-Liang Chung and
Wen-Ming Yan Fast $2$D discrete cosine transform on
compressed image in restricted quadtree
and shading format . . . . . . . . . . . 13--21
Yaoyun Shi Entropy lower bounds for quantum
decision tree complexity . . . . . . . . 23--27
Jerzy Skurczy\'nski A characterization of Büchi tree automata 29--33
Arturo Carpi and
Aldo de Luca A combinatorial property of the factor
poset of a word . . . . . . . . . . . . 35--39
Chien-Lung Hsu and
Tzong-Sun Wu and
Tzong-Chen Wu Improvements of generalization of
threshold signature and authenticated
encryption for group communications . . 41--45
Michael J. Spriggs and
J. Mark Keil A new bound for map labeling with
uniform circle pairs . . . . . . . . . . 47--53
Alain Bretto and
Stéphane Ubéda and
Janez \vZerovnik A polynomial algorithm for the strong
Helly property . . . . . . . . . . . . . 55--57
Jürgen Branke and
Stefan Leppert and
Martin Middendorf and
Peter Eades Width-restricted layering of acyclic
digraphs with consideration of dummy
nodes . . . . . . . . . . . . . . . . . 59--63
Pascal Koiran Transfer theorems via sign conditions 65--69
John Noga and
Steve Seiden and
Gerhard J. Woeginger A faster off-line algorithm for the TCP
acknowledgement problem . . . . . . . . 71--73
Holger Petersen Bounds for the Element Distinctness
Problem on one-tape Turing machines . . 75--79
Aleksander Bachman and
Adam Janiak and
Mikhail Y. Kovalyov Minimizing the total weighted completion
time of deteriorating jobs . . . . . . . 81--84
Noritaka Kobayashi and
Tatsuhiro Tsuchiya and
Tohru Kikuno A new method for constructing pair-wise
covering designs for software testing 85--91
The Eindhoven Tuesday Afternoon Club On computing a longest path in a tree 93--96
Tae-Sun Chung and
Hyoung-Joo Kim Extracting indexing information from XML
DTDs . . . . . . . . . . . . . . . . . . 97--103
Wei Lai and
Peter Eades Removing edge-node intersections in
drawings of graphs . . . . . . . . . . . 105--110
D. Goswami and
R. Mall An efficient method for computing
dynamic program slices . . . . . . . . . 111--117
Jörg Keller A heuristic to accelerate in-situ
permutation algorithms . . . . . . . . . 119--125
Fredrik Jönsson and
Thomas Johansson A fast correlation attack on LILI-128 127--132
Qi Cheng and
Fang Fang Kolmogorov random graphs only have
trivial stable colorings . . . . . . . . 133--136
Joachim Gudmundsson and
Thore Husfeldt and
Christos Levcopoulos Lower bounds for approximate polygon
decomposition and minimum gap . . . . . 137--141
Oh-Heum Kwon and
Kyung-Yong Chwa Approximation algorithms for general
parallel task scheduling . . . . . . . . 143--150
Lusheng Wang and
Zimao Li An approximation algorithm for a
bottleneck $k$-Steiner tree problem in
the Euclidean plane . . . . . . . . . . 151--156
Ho\`ang-Oanh Le and
Van Bang Le The NP-completeness of $(1,
r)$-subcolorability of cubic graphs . . 157--162
Marco Cesati Perfect Code is $W[1]$-complete . . . . 163--168
Gordon Lyon Comparison of two code scalability tests 169--174
Judit Büki and
Csaba Szabó Complexity of homomorphisms to direct
products of graphs . . . . . . . . . . . 175--178
Oukseh Lee and
Kwangkeun Yi and
Yunheung Paek A proof method for the correctness of
modularized 0CFA . . . . . . . . . . . . 179--185
Toru Araki and
Yukio Shibata Pancyclicity of recursive circulant
graphs . . . . . . . . . . . . . . . . . 187--190
San Skulrattanakulchai $4$-edge-coloring graphs of maximum
degree $3$ in linear time . . . . . . . 191--195
Chip Martel The expected complexity of Prim's
minimum spanning tree algorithm . . . . 197--201
Fanica Gavril Algorithms for maximum weight induced
paths . . . . . . . . . . . . . . . . . 203--208
Soumen Maity and
Bimal K. Roy and
Amiya Nayak On enumeration of catastrophic fault
patterns . . . . . . . . . . . . . . . . 209--212
Susanne Albers and
Marek Karpinski Randomized splay trees: Theoretical and
experimental results . . . . . . . . . . 213--221
Alfredo García Olaverri and
Ferran Hurtado and
Marc Noy and
Javier Tejel On the minimum size of visibility graphs 223--230
Zenji Kobayashi and
Takeshi Sekiguchi On a characterization of the standard
Gray code by using its edge type on a
hypercube . . . . . . . . . . . . . . . 231--237
Dong-Ho Lee and
Hyoung-Joo Kim An efficient nearest neighbor search in
high-dimensional data spaces . . . . . . 239--246
Refael Hassin and
Shlomi Rubinstein A $\frac{7}{8}$-approximation algorithm
for metric Max TSP . . . . . . . . . . . 247--251
A. Meduna and
D. Kolá\vr Homogeneous grammars with a reduced
number of non-context-free productions 253--257
Mark de Berg and
A. Frank van der Stappen On the fatness of Minkowski sums . . . . 259--264
Jae-Ha Lee and
Sang-Min Park and
Kyung-Yong Chwa Simple algorithms for searching a
polygon with flashlights . . . . . . . . 265--270
Hai Zhou and
Narendra Shenoy and
William Nicholls Efficient minimum spanning tree
construction without Delaunay
triangulation . . . . . . . . . . . . . 271--276
Aleksander Vesel and
Janez \vZerovnik Improved lower bound on the Shannon
capacity of $C_7$ . . . . . . . . . . . 277--282
N. Kitsios and
others An optimal algorithm for reporting
visible rectangles . . . . . . . . . . . 283--288
N. Kitsios and
C. Makris and
S. Sioutas and
A. Tsakalidis and
J. Tsaknakis and
B. Vassiliadis An optimal algorithm for reporting
visible rectangles . . . . . . . . . . . 283--288
A. Koubková and
V. Koubek Algorithms for transitive closure . . . 289--296
Edwin Naroska and
Uwe Schwiegelshohn On an on-line scheduling problem for
parallel jobs . . . . . . . . . . . . . 297--304
Rezaul Alam Chowdhury and
M. Kaykobad and
Irwin King An efficient decoding technique for
Huffman codes . . . . . . . . . . . . . 305--308
Éric Sopena There exist oriented planar graphs with
oriented chromatic number at least
sixteen . . . . . . . . . . . . . . . . 309--312
Ilyong Chung and
Wankyu Choi and
Youngchel Kim and
Mike Lee The design of conference key
distribution system employing a
symmetric balanced incomplete block
design . . . . . . . . . . . . . . . . . 313--318
Andrew G. Hart and
Servet Martínez Sequential iteration of the Erlang
fixed-point equations . . . . . . . . . 319--325
C. T. Ng and
T. C. E. Cheng and
A. Bachman and
A. Janiak Three scheduling problems with
deteriorating jobs to minimize the total
completion time . . . . . . . . . . . . 327--333
Bruno Zanuttini and
Jean-Jacques Hébrard A unified framework for structure
identification . . . . . . . . . . . . . 335--339
Kurt Mehlhorn and
Volker Priebe and
Guido Schäfer and
Naveen Sivadasan All-pairs shortest-paths computation in
the presence of negative cycles . . . . 341--343
Anonymous Subject Index --- Volume 81 (2002) . . . 345--346
Anonymous Author Index --- Volume 81 (2002) . . . 347--349
A. E. Eiben and
M. Schoenauer Evolutionary computing . . . . . . . . . 1--6
Enrique Alba Parallel evolutionary algorithms can
achieve super-linear performance . . . . 7--13
Erick Cantú-Paz Order statistics and selection methods
of evolutionary algorithms . . . . . . . 15--22
John H. Holmes and
Pier Luca Lanzi and
Wolfgang Stolzmann and
Stewart W. Wilson Learning classifier systems: New models,
successful applications . . . . . . . . 23--30
Vili Podgorelec and
Peter Kokol Evolutionary induced decision trees for
dangerous software modules prediction 31--38
Günther R. Raidl and
Ivana Ljubi\'c Evolutionary local search for the
edge-biconnectivity augmentation problem 39--45
Shisanu Tongchim and
Prabhas Chongstitvatana Parallel genetic algorithm with
parameter adaptation . . . . . . . . . . 47--54
Anjan Kumar Swain and
Alan S. Morris Performance improvement of self-adaptive
evolutionary methods with a dynamic
lower bound . . . . . . . . . . . . . . 55--63
Keon-Jik Lee and
Kee-Won Kim and
Kee-Young Yoo Digit-serial-in-serial-out systolic
multiplier for Montgomery algorithm . . 65--71
Tsorng-Lin Chia and
Kuang-Bor Wang and
Zen Chen and
Der-Chyuan Lou Parallel distance transforms on a linear
array architecture . . . . . . . . . . . 73--81
W. Zimmermann and
W. Löwe and
D. Trystram On scheduling send-graphs and
receive-graphs under the LogP-model . . 83--92
Peter Damaschke Optimizing a mail-order with discount
and shipping costs . . . . . . . . . . . 93--97
Stephan Eidenbenz Approximation algorithms for terrain
guarding . . . . . . . . . . . . . . . . 99--105
Zhaohui Liu and
T. C. Edwin Cheng Scheduling with job release dates,
delivery times and preemption penalties 107--111
Jianxi Fan Hamilton-connectivity and
cycle-embedding of the Möbius cubes . . . 113--117
Andreas Brandstädt and
Ho\`ang-Oanh Le and
Van Bang Le On $\alpha$-redundant vertices in
$P_5$-free graphs . . . . . . . . . . . 119--122
A. C. Patthak and
I. Bhattacharya and
A. Dasgupta and
Pallab Dasgupta and
P. P. Chakrabarti Quantified Computation Tree Logic . . . 123--129
Sun-yuan Hsieh On vertex ranking of a starlike graph 131--135
Håkan Jonsson The Traveling Salesman Problem for lines
in the plane . . . . . . . . . . . . . . 137--142
John P. Fishburn Solving a system of difference
constraints with variables restricted to
a finite set . . . . . . . . . . . . . . 143--144
Walter J. Gutjahr ACO algorithms with guaranteed
convergence to the optimal solution . . 145--153
Shao-Chin Sung and
Keisuke Tanaka An exponential gap with the removal of
one negation gate . . . . . . . . . . . 155--157
Dan Gusfield Partition-distance: A problem and class
of perfect graphs arising in clustering 159--164
Jörg Rothe and
Lane A. Hemaspaandra On characterizing the existence of
partial one-way permutations . . . . . . 165--171
Y. H. Tsin Some remarks on distributed depth-first
search . . . . . . . . . . . . . . . . . 173--178
Ji-Woong Chang and
Young-Koo Lee and
Kyu-Young Whang Global lock escalation in database
management systems . . . . . . . . . . . 179--186
C. T. Ng and
T. C. E. Cheng and
J. J. Yuan Strong NP-hardness of the single machine
multi-operation jobs total completion
time scheduling problem . . . . . . . . 187--191
Martin Richards A note concerning the closest point pair
algorithm . . . . . . . . . . . . . . . 193--195
Cedric Chauve Tree pattern matching with a more
general notion of occurrence of the
pattern . . . . . . . . . . . . . . . . 197--201
Paulo A. S. Veloso and
José L. Fiadeiro and
Sheila R. M. Veloso On local modularity and interpolation in
entailment systems . . . . . . . . . . . 203--211
Yangjun Chen Signature files and signature trees . . 213--221
Arnaldo V. Moura and
Guilherme A. Pinto A note on the verification of automata
specifications of probabilistic
real-time systems . . . . . . . . . . . 223--228
Jérôme Monnot Differential approximation results for
the traveling salesman and related
problems . . . . . . . . . . . . . . . . 229--235
Paolo Penna On the approximability of two tree
drawing conventions . . . . . . . . . . 237--242
Seokhie Hong and
Jaechul Sung and
Sangjin Lee and
Jongin Lim and
Jongsu Kim Provable security for $13$ round
Skipjack-like structure . . . . . . . . 243--246
Taekyoung Kwon Digital signature algorithm for securing
digital identities . . . . . . . . . . . 247--252
Amihood Amir and
Gad M. Landau and
Esko Ukkonen Online timestamped text indexing . . . . 253--259
James P. Delgrande and
Arvind Gupta Updating $\leq$-chains . . . . . . . . . 261--268
Harald Kosch and
Solomon Atnafu Processing a multimedia join through the
method of nearest neighbor search . . . 269--276
Jerry L. Trahan and
Ramachandran Vaidyanathan Scaling multiple addition and prefix
sums on the reconfigurable mesh . . . . 277--282
Thomas Eiter and
Toshihide Ibaraki and
Kazuhisa Makino Recognition and dualization of disguised
bidual Horn functions . . . . . . . . . 283--291
Xiao Yu Li and
Matthias F. Stallmann New bounds on the barycenter heuristic
for bipartite graph drawing . . . . . . 293--298
Emmanuel Godard A self-stabilizing enumeration algorithm 299--305
S. Srinivasa Rao Time-space trade-offs for compressed
suffix arrays . . . . . . . . . . . . . 307--311
Yves Métivier and
Nasser Saheb and
Akka Zemmari Randomized local elections . . . . . . . 313--320
Manindra Agrawal For completeness, sublogarithmic space
is no space . . . . . . . . . . . . . . 321--325
William M. Y. Goh and
Pawe\l Hitczenko and
Ali Shokoufandeh $s$-partitions . . . . . . . . . . . . . 327--329
Anonymous Subject Index ---- Volume 82 (2002) . . 331--332
Anonymous Author Index ---- Volume 82 (2002) . . . 333--334
Arnaud Lefebvre and
Thierry Lecroq Compror: On-line lossless data
compression with a factor oracle . . . . 1--6
Harald Fecher and
Mila Majster-Cederbaum and
Jinzhao Wu Bundle event structures: A revised cpo
approach . . . . . . . . . . . . . . . . 7--12
Alan J. Hoffman and
Kate Jenkins and
Tim Roughgarden On a game in directed graphs . . . . . . 13--16
Ingo Wegener A simplified correctness proof for a
well-known algorithm computing strongly
connected components . . . . . . . . . . 17--19
Atsushi Sasaki A time-optimal distributed sorting
algorithm on a line network . . . . . . 21--26
Ivan D. Baev and
Waleed M. Meleis and
Alexandre Eichenberger Lower bounds on precedence-constrained
scheduling for parallel processors . . . 27--32
Amihood Amir and
Moshe Lewenstein and
Ely Porat Approximate swapped matching . . . . . . 33--39
Maharaj Mukherjee and
Kanad Chakraborty A polynomial-time optimization algorithm
for a rectilinear partitioning problem
with applications in VLSI design
automation . . . . . . . . . . . . . . . 41--48
Haengrae Cho Database recovery using incomplete page
versions in a multisystem data sharing
environment . . . . . . . . . . . . . . 49--55
Fedor V. Fomin and
Andrzej Lingas Approximation algorithms for
time-dependent orienteering . . . . . . 57--62
Bruno Carpentieri Sending compressed messages to a learned
receiver on a bidirectional line . . . . 63--70
Tatsuhiro Tsuchiya and
Tohru Kikuno Byzantine quorum systems with maximum
availability . . . . . . . . . . . . . . 71--77
Byeong-Mo Chang Managing the granularity of
constraint-based analyses by rule
transformation . . . . . . . . . . . . . 79--88
Leszek G\kasieniec and
Andrzej Lingas On adaptive deterministic gossiping in
ad hoc radio networks . . . . . . . . . 89--93
Wei-Hua He Weaknesses in some multisignature
schemes for specified group of verifiers 95--99
R. Barbuti and
C. Bernardeschi and
N. De Francesco Abstract interpretation of operational
semantics for secure information flow 101--108
Igor E. Shparlinski Security of most significant bits of
$g^{x^2}$ . . . . . . . . . . . . . . . 109--113
Dong-Ho Lee and
Shin Heu and
Hyoung-Joo Kim An efficient algorithm for
hyperspherical range query processing in
high-dimensional data space . . . . . . 115--123
Matthieu Latapy and
Clémence Magnien Coding distributive lattices with Edge
Firing Games . . . . . . . . . . . . . . 125--128
Marek Piotrów A note on constructing binary heaps with
periodic networks . . . . . . . . . . . 129--134
L. Paul Chew and
Haggai David and
Matthew J. Katz and
Klara Kedem Walking around fat obstacles . . . . . . 135--140
Francis Y. L. Chin and
Fu Lee Wang Efficient algorithm for transversal of
disjoint convex polygons . . . . . . . . 141--144
Rafael Dueire Lins An efficient algorithm for cyclic
reference counting . . . . . . . . . . . 145--150
Ricardo A. Baeza-Yates and
Héctor Soza-Pollman Optimal bounded disorder . . . . . . . . 151--157
Alberto Apostolico and
Stefano Lonardi A speed-up for the commute between
subword trees and DAWGs . . . . . . . . 159--161
Mohammad Taghi Hajiaghayi and
Yashar Ganjali A note on the Consecutive Ones Submatrix
problem . . . . . . . . . . . . . . . . 163--166
P. Y. Schobbens and
G. Saake and
A. Sernadas and
C. Sernadas A two-level temporal logic for evolving
specifications . . . . . . . . . . . . . 167--172
Claudio Arbib and
Alberto Caprara On the stability number of the edge
intersection of two graphs . . . . . . . 173--174
Navneet Malpani and
Jianer Chen A note on practical construction of
maximum bandwidth paths . . . . . . . . 175--180
Anonymous Note from the Publisher . . . . . . . . 181--181
Boris Aronov A lower bound on Voronoi diagram
complexity . . . . . . . . . . . . . . . 183--185
Fabian Schwarzer and
Achim Schweikard On the complexity of one-shot
translational separability . . . . . . . 187--194
Clemens Gröpl and
Stefan Hougardy and
Till Nierhoff and
Hans Jürgen Prömel Steiner trees in uniformly
quasi-bipartite graphs . . . . . . . . . 195--200
Jean-Luc Fouquet No odd pairs in minimal imperfect NP$_5$
graphs . . . . . . . . . . . . . . . . . 201--204
Eduardo Sany Laber and
Leonardo Gomes Holanda Improved bounds for asymmetric
communication protocols . . . . . . . . 205--209
John D. Holt and
Soon M. Chung Mining association rules using inverted
hashing and pruning . . . . . . . . . . 211--220
Paul Attie Wait-free Byzantine consensus . . . . . 221--227
Mikhail Y. Kovalyov and
Marcus Pattloch and
Günter Schmidt A polynomial algorithm for lot-size
scheduling of two type tasks . . . . . . 229--235
Benny K. Nielsen and
Pawel Winter and
Martin Zachariasen On the location of Steiner points in
uniformly-oriented Steiner trees . . . . 237--241
Francesco Quaglia A restriction of the elastic time
algorithm . . . . . . . . . . . . . . . 243--249
Ph. Schnoebelen Verifying lossy channel systems has
nonprimitive recursive complexity . . . 251--261
S. Galbraith and
J. Malone-Lee and
N. P. Smart Public key signatures in the multi-user
setting . . . . . . . . . . . . . . . . 263--266
Amnon Ta-Shma Storing information with extractors . . 267--274
Ioannis Caragiannis and
Christos Kaklamanis and
Panagiotis Kanellopoulos New bounds on the size of the minimum
feedback vertex set in meshes and
butterflies . . . . . . . . . . . . . . 275--280
Subhamoy Maitra Highly nonlinear balanced Boolean
functions with good local and global
avalanche characteristics . . . . . . . 281--286
Funda Ergun and
Rakesh Sinha and
Lisa Zhang An improved FPTAS for Restricted
Shortest Path . . . . . . . . . . . . . 287--291
Gerard J. Chang Corrigendum to ``The path-partition
problem in block graphs'': [Information
Processing Letters \bf 52 (1994)
317--322] . . . . . . . . . . . . . . . 293--293
Shahrokh Saeednia An identity-based society oriented
signature scheme with anonymous signers 295--299
Chang-Hsiung Tsai and
Jimmy J. M. Tan and
Tyne Liang and
Lih-Hsing Hsu Fault-tolerant Hamiltonian laceability
of hypercubes . . . . . . . . . . . . . 301--306
Ora Arbell and
Gad M. Landau and
Joseph S. B. Mitchell Edit distance of run-length encoded
strings . . . . . . . . . . . . . . . . 307--314
Chor Ping Low An efficient retrieval selection
algorithm for video servers with random
duplicated assignment storage technique 315--321
Zhiyi Tan and
Yong He Optimal online algorithm for scheduling
on two identical machines with machine
availability constraints . . . . . . . . 323--329
Loren Schwiebert There is no optimal routing policy for
the torus . . . . . . . . . . . . . . . 331--336
Sheng-Tzong Cheng and
Ing-Ray Chen A self-adjusting quality of service
control scheme . . . . . . . . . . . . . 337--344
Carles Padró and
Germán Sáez Lower bounds on the information rate of
secret sharing schemes with homogeneous
access structure . . . . . . . . . . . . 345--351
Anonymous Subject Index ---- Volume 83 (2002) . . 353--354
Anonymous Author Index ---- Volume 83 (2002) . . . 355--356
Elvira Mayordomo A Kolmogorov complexity characterization
of constructive Hausdorff dimension . . 1--3
Mauricio Ayala-Rincón and
Alexsandro F. da Fonseca and
Haydée Werneck Poubel and
José Siqueira A framework to visualize equivalences
between computational models of regular
languages . . . . . . . . . . . . . . . 5--16
Takeshi Kanda and
Kokichi Sugihara Comparison of various trees for
nearest-point search with/without the
Voronoi diagram . . . . . . . . . . . . 17--22
S. S. Bansal and
B. Vishal and
P. Gupta Near optimal Cholesky factorization on
orthogonal multiprocessors . . . . . . . 23--30
Jun Gu and
Xiao-Dong Hu and
Mu-Hong Zhang Algorithms for multicast connection
under multi-path routing model . . . . . 31--39
Ronald I. Greenberg and
Lee Guan On the area of hypercube layouts . . . . 41--46
Yong-Jik Kim and
James H. Anderson A space- and time-efficient local-spin
spin lock . . . . . . . . . . . . . . . 47--55
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Juha Honkala The equality problem for Parikh simple
algebraic power series . . . . . . . . . 57--60
Gregory Karagiorgos and
Nikolaos M. Missirlis Accelerated diffusion algorithms for
dynamic load balancing . . . . . . . . . 61--67
Lars Jacobsen and
Kim S. Larsen and
Morten N. Nielsen On the existence and construction of
non-extreme $(a,b)$-trees . . . . . . . 69--73
Patricia Bouyer A logical characterization of data
languages . . . . . . . . . . . . . . . 75--85
Yen-Chu Chuang and
Lih-Hsing Hsu and
Chung-Haw Chang Optimal $1$-edge fault-tolerant designs
for ladders . . . . . . . . . . . . . . 87--92
Anand Srinivasan and
Sanjoy Baruah Deadline-based scheduling of periodic
task systems on multiprocessors . . . . 93--98
Yingyu Wan and
Guoliang Chen and
Yinlong Xu A note on the minimum label spanning
tree . . . . . . . . . . . . . . . . . . 99--101
Guohui Lin and
Guoliang Xue On the terminal Steiner tree problem . . 103--107
Oh-Heum Kwon Scheduling time-constrained multicast
messages in circuit-switched tree
networks . . . . . . . . . . . . . . . . 109--116
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Eli Biham How to decrypt or even substitute
DES-encrypted messages in $2^{28}$ steps 117--124
Seung Mo Cho and
Hyung Ho Kim and
Sung Deok Cha and
Doo Hwan Bae A semantics of sequence diagrams . . . . 125--130
Guillaume Fertin and
Emmanuel Godard and
André Raspaud Minimum feedback vertex set and acyclic
coloring . . . . . . . . . . . . . . . . 131--139
Zhi-Zhong Chen and
Shiqing Zhang Tight upper bound on the number of edges
in a bipartite $K_{3,3}$-free or
K$_5$-free graph with an application . . 141--145
Hans Kleine Büning and
Xishun Zhao Polynomial time algorithms for computing
a representation for minimal
unsatisfiable formulas with fixed
deficiency . . . . . . . . . . . . . . . 147--151
Oded Regev Priority algorithms for makespan
minimization in the subset model . . . . 153--157
Roberto Baldoni and
Giovanna Melideo On the minimal information to encode
timestamps in distributed computations 159--166
Shin-ichi Nakano Efficient generation of plane trees . . 167--172
Tom Araki and
Yukio Shibata Erratum to: ``Pancyclicity of recursive
circulant graphs'': [Inform. Process.
Lett. \bf 81 (2002) 187--190] . . . . . 173--173
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Alberto Caprara and
Romeo Rizzi Packing triangles in bounded degree
graphs . . . . . . . . . . . . . . . . . 175--180
Jakub Neumann and
Andrzej Szepietowski and
Igor Walukiewicz Complexity of weak acceptance conditions
in tree automata . . . . . . . . . . . . 181--187
Kazuhisa Makino and
Takashi Takabatake and
Satoru Fujishige A simple matching algorithm for regular
bipartite graphs . . . . . . . . . . . . 189--193
Yin-Te Tsai and
Yaw-Ling Lin and
F. R. Hsu The on-line first-fit algorithm for
radio frequency assignment problems . . 195--199
Sunil Arya Binary space partitions for
axis-parallel line segments: Size-height
tradeoffs . . . . . . . . . . . . . . . 201--206
Enno Ohlebusch Hierarchical termination revisited . . . 207--214
Samir Khuller and
An Zhu The General Steiner Tree-Star problem 215--220
Minyoung Sung and
Soyoung Kim and
Sangsoo Park and
Naehyuck Chang and
Heonshik Shin Comparative performance evaluation of
Java threads for embedded applications:
Linux Thread vs. Green Thread . . . . . 221--225
Rakesh Verma Algorithms and reductions for rewriting
problems. II . . . . . . . . . . . . . . 227--233
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Oliver Pretzel Characterization of simple edge-firing
games . . . . . . . . . . . . . . . . . 235--236
Adi Rosén A note on models for non-probabilistic
analysis of packet switching networks 237--240
Stefania Costantini and
Ottavio D'Antona and
Alessandro Provetti On the equivalence and range of
applicability of graph-based
representations of logic programs . . . 241--249
Andreas Brandstädt and
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
Ken-etsu Fujita An interpretation of
$\lambda^\mu$-calculus in
$\lambda$-calculus . . . . . . . . . . . 261--264
Hung Quang Ngo and
Ding-Zhu Du and
Ronald L. Graham New bounds on a hypercube coloring
problem . . . . . . . . . . . . . . . . 265--269
Yair Bartal and
Marek Chrobak and
John Noga and
Prabhakar Raghavan More on random walks, electrical
networks, and the harmonic $k$-server
algorithm . . . . . . . . . . . . . . . 271--276
Hsun-Jung Cho and
Li-Yen Hsu Ring embedding in faulty honeycomb
rectangular torus . . . . . . . . . . . 277--284
Fedor V. Fomin and
Dieter Kratsch and
Jean-Christophe Novelli Approximating minimum cocolorings . . . 285--290
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Daniel Kirsten The finite power problem revisited . . . 291--294
Prasanta K. Jana and
B. Damodara Naidu and
Shailendra Kumar and
Monish Arora and
Bhabani P. Sinha Parallel prefix computation on extended
multi-mesh network . . . . . . . . . . . 295--303
Andrea Maggiolo-Schettini and
Simone Tini On disjunction of literals in triggers
of statecharts transitions . . . . . . . 305--310
Antoni Diller Efficient multi-variate abstraction
using an array representation for
combinators . . . . . . . . . . . . . . 311--317
Carlo Blundo and
Stelvio Cimato and
Barbara Masucci A note on optimal metering schemes . . . 319--326
A. L. Rastsvetaev and
L. D. Beklemishev On the query complexity of finding a
local maximum point . . . . . . . . . . 327--332
Sean Cleary Restricted rotation distance between
binary trees . . . . . . . . . . . . . . 333--338
Michael Domaratzki and
Giovanni Pighizzini and
Jeffrey Shallit Simulating finite automata with
context-free grammars . . . . . . . . . 339--344
Anonymous Subject Index ---- Volume 84 (2002) . . 345--346
Anonymous Author Index ---- Volume 84 (2002) . . . 347--349
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Dimitris J. Kavvadias and
Elias C. Stavropoulos Monotone Boolean dualization is in
$\mathrm{co-NP}[\log^2 n]$ . . . . . . . 1--6
Jun-Ki Min and
Jae-Yong Ahn and
Chin-Wan Chung Efficient extraction of schemas for XML
documents . . . . . . . . . . . . . . . 7--12
Wilfried Meidl and
Arne Winterhof On the linear complexity profile of
explicit nonlinear pseudorandom numbers 13--18
Elvira Albert and
Michael Hanus and
Germán Vidal A residualizing semantics for the
partial evaluation of functional logic
programs . . . . . . . . . . . . . . . . 19--25
Cheng-Yuan Ku and
Din-Yuen Chan and
Lain-Chyr Hwang Optimal reservation policy for two
queues in tandem . . . . . . . . . . . . 27--30
Jae-Hoon Kim and
Kyung-Yong Chwa Online deadline scheduling on faster
machines . . . . . . . . . . . . . . . . 31--37
Edgar Chávez and
Gonzalo Navarro Probabilistic proximity search: Fighting
the curse of dimensionality in metric
spaces . . . . . . . . . . . . . . . . . 39--46
Idit Keidar and
Sergio Rajsbaum A simple proof of the uniform consensus
synchronous lower bound . . . . . . . . 47--52
Francis Y. L. Chin and
Fu Lee Wang Erratum to: ``Efficient algorithm for
transversal of disjoint convex
polygons'' . . . . . . . . . . . . . . . 53--53
Francis Y. L. Chin and
Hong Shen and
Fu Lee Wang Transversal of disjoint convex polygons 55--60
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
G. Richomme Some non finitely generated monoids of
repetition-free endomorphisms . . . . . 61--66
Amitai Armon and
Yossi Azar and
Leah Epstein and
Oded Regev On-line restricted assignment of
temporary tasks with unknown durations 67--72
Marianne Durand Asymptotic analysis of an optimized
quicksort algorithm . . . . . . . . . . 73--77
K. Vidyasankar A simple group mutual $l$-exclusion
algorithm . . . . . . . . . . . . . . . 79--85
Antoine Vigneron Reporting intersections among thick
objects . . . . . . . . . . . . . . . . 87--92
Jong Min Kim and
Donghee Lee and
Sam H. Noh and
Sang Lyul Min and
Yookun Cho and
Chong Sang Kim An accurate and practical buffer
allocation model for the buffer cache
based on marginal gains . . . . . . . . 93--97
Chin-Chen Chang and
Chi-Yien Chung An efficient protocol for anonymous
multicast and reception . . . . . . . . 99--103
Y. P. Aneja and
R. Chandrasekaran and
K. P. K. Nair Parametric analysis of overall min-cuts
and applications in undirected networks 105--109
Amparo Fúster-Sabater and
Pedro García-Mochales On the balancedness of nonlinear
generators of binary sequences . . . . . 111--116
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Wlodzimierz Ogryczak and
Arie Tamir Minimizing the sum of the $k$ largest
functions in linear time . . . . . . . . 117--122
Hél\`ene Touzet Tree edit distance with gaps . . . . . . 123--129
Ying Miao A combinatorial characterization of
regular anonymous perfect threshold
schemes . . . . . . . . . . . . . . . . 131--135
Zuhua Shao Proxy signature schemes based on
factoring . . . . . . . . . . . . . . . 137--143
Dhananjay M. Dhamdhere and
K. Gururaja and
Prajakta G. Ganu A compact execution history for dynamic
slicing . . . . . . . . . . . . . . . . 145--152
Chris Giannella and
Edward Robertson A note on approximation measures for
multi-valued dependencies in relational
databases . . . . . . . . . . . . . . . 153--158
Tsung-Chuan Huang and
Slo-Li Chu A statement based parallelizing
framework for processor-in-memory
architectures . . . . . . . . . . . . . 159--163
Guilherme D. da Fonseca and
Celina M. H. de Figueiredo Kinetic heap-ordered trees: Tight
analysis and improved algorithms . . . . 165--169
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Deshi Ye and
Guochuan Zhang On-line scheduling with extendable
working time on a small number of
machines . . . . . . . . . . . . . . . . 171--177
Gennady Pustylnik and
Micha Sharir The Minkowski sum of a simple polygon
and a segment . . . . . . . . . . . . . 179--184
Chang-Chun Lu and
Shi-Chun Tsai A note on unscrambling address lines . . 185--189
Takashi Horiyama and
Toshihide Ibaraki Translation among CNFs, characteristic
models and ordered binary decision
diagrams . . . . . . . . . . . . . . . . 191--198
Satoshi Fujita On-line grid-packing with a single
active grid . . . . . . . . . . . . . . 199--204
Po-Hsueh Huang and
Yin Te Tsai and
Chuan Yi Tang A fast algorithm for the alpha-connected
two-center decision problem . . . . . . 205--210
Doratha E. Drake and
Stefan Hougardy A simple approximation algorithm for the
weighted matching problem . . . . . . . 211--213
Jong Ha Ko and
Sang Hee Kim and
Jong Kyu Lee An ENA algorithm to enhance the
performance of TCP over satellite links 215--219
Jurriaan Hage Enumerating submultisets of multisets 221--226
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Richard Cole and
Costas Iliopoulos and
Thierry Lecroq and
Wojciech Plandowski and
Wojciech Rytter On special families of morphisms related
to $\delta$-matching and don't care
symbols . . . . . . . . . . . . . . . . 227--233
Jean Pallo Generating binary trees by Glivenko
classes on Tamari lattices . . . . . . . 235--238
Ferdinando Cicalese and
Ugo Vaccaro Binary search with delayed and missing
answers . . . . . . . . . . . . . . . . 239--247
Jan Poland Finding smooth maps is NP-complete . . . 249--253
Jayadev Misra Derivation of a parallel string matching
algorithm . . . . . . . . . . . . . . . 255--260
Guillaume Fertin and
André Raspaud and
Arup Roychowdhury On the oriented chromatic number of
grids . . . . . . . . . . . . . . . . . 261--266
Ming Li and
John Tromp and
Paul Vitányi Sharpening Occam's razor . . . . . . . . 267--274
Desh Ranjan and
Enrico Pontelli The Level-Ancestor problem on Pure
Pointer Machines . . . . . . . . . . . . 275--283
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Olivier Serre Note on winning positions on pushdown
games with $\omega$-regular conditions 285--291
Yuri Lifshits A lower bound on the size of
$\epsilon$-free NFA corresponding to a
regular expression . . . . . . . . . . . 293--299
Noga Alon A simple algorithm for edge-coloring
bipartite multigraphs . . . . . . . . . 301--302
Therese Biedl and
Timothy M. Chan and
Alejandro López-Ortiz Drawing $K_{2,n}$: A lower bound . . . . 303--305
Mayur Datar and
Tomás Feder and
Aristides Gionis and
Rajeev Motwani and
Rina Panigrahy A combinatorial algorithm for MAX CSP 307--315
Ioan Cristian Trelea The particle swarm optimization
algorithm: convergence analysis and
parameter selection . . . . . . . . . . 317--325
Markus Bläser Computing small partial coverings . . . 327--331
Sinichiro Kawano and
Koichi Yamazaki Worst case analysis of a greedy
algorithm for graph thickness . . . . . 333--337
C. S. Laih and
S. Y. Chiou Cryptanalysis of an optimized protocol
for mobile network authentication and
security . . . . . . . . . . . . . . . . 339--341
Anonymous Subject Index ---- Volume 85 (2003) . . 343--344
Anonymous Author Index ---- Volume 85 (2003) . . . 345--347
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Yongsu Park and
Tae-Sun Chung and
Yookun Cho An efficient stream authentication
scheme using tree chaining . . . . . . . 1--8
John M. Hitchcock Gales suffice for constructive dimension 9--12
Zakil Koo and
Songchun Moon Effects of broadcast errors on
concurrency control in wireless
broadcasting environments . . . . . . . 13--21
Stephen Kwek and
Kurt Mehlhorn Optimal search for rationals . . . . . . 23--26
C. K. Poon Verifying minimum stable circuit values 27--32
Peter Sanders and
Jop F. Sibeyn A bandwidth latency tradeoff for
broadcast and reduction . . . . . . . . 33--38
P. Krishna Reddy and
Masaru Kitsuregawa Reducing the blocking in two-phase
commit with backup sites . . . . . . . . 39--47
Rajgopal Kannan and
S. Sarangi and
Sibabrata Ray and
S. S. Iyengar Minimal sensor integrity: Measuring the
vulnerability of sensor grids . . . . . 49--55
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Kazuhiro Ogata and
Kokichi Futatsugi Flaw and modification of the $i$ KP
electronic payment protocols . . . . . . 57--62
Liang Zhao and
Hiroshi Nagamochi and
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 and
Yukio Shibata On the domination numbers of generalized
de Bruijn digraphs and generalized Kautz
digraphs . . . . . . . . . . . . . . . . 79--85
Daya Ram Gaur and
Arvind Gupta and
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 and
Romeo Rizzi On the complexity of digraph packings 101--106
Scott Effler and
Frank Ruskey A CAT algorithm for generating
permutations with a fixed number of
inversions . . . . . . . . . . . . . . . 107--112
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
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 and
Irene Finocchi Combinatorial algorithms for feedback
problems in directed graphs . . . . . . 129--136
Axel Born and
Cor A. J. Hurkens and
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 and
Christos Kaklamanis and
Panagiotis Kanellopoulos A logarithmic approximation algorithm
for the minimum energy consumption
broadcast subgraph problem . . . . . . . 149--154
L.-B. Chen An efficient minimum and maximum global
snapshot algorithm . . . . . . . . . . . 155--159
Andreas Brandstädt and
Ho\`ang-Oanh Le and
Jean-Marie Vanherpe Structure and stability number of
chair-, co-P- and gem-free graphs
revisited . . . . . . . . . . . . . . . 161--167
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Roy Friedman and
Roman Vitenberg and
Gregory Chockler On the composability of consistency
conditions . . . . . . . . . . . . . . . 169--176
Li Lin and
Yunfei Jiang The computation of hitting sets: Review
and new algorithms . . . . . . . . . . . 177--184
Hsun-Jung Cho and
Li-Yen Hsu Generalized honeycomb torus . . . . . . 185--190
Rastislav Královi\vc and
Peter Ru\vzi\vcka Minimum feedback vertex sets in
shuffle-based interconnection networks 191--196
Susanne E. Hambrusch and
Chuan-Ming Liu Data replication in static tree
structures . . . . . . . . . . . . . . . 197--202
Esther M. Arkin and
Joseph S. B. Mitchell and
Christine D. Piatko Minimum-link watchman tours . . . . . . 203--207
Christos Makris and
Athanasios Tsakalidis and
Kostas Tsichlas Reflected min-max heaps . . . . . . . . 209--214
Luc Devroye and
Pat Morin Cuckoo hashing: Further analysis . . . . 215--219
Stefan D. Bruda and
Selim G. Akl On limits on the computational power of
data-accumulating algorithms . . . . . . 221--227
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Rafiqul Islam and
Nasim Adnan and
Nur Islam and
Shohorab Hossen A new external sorting algorithm with no
additional disk space . . . . . . . . . 229--233
H. Fernau and
A. Meduna A simultaneous reduction of several
measures of descriptional complexity in
scattered context grammars . . . . . . . 235--240
S. Mantaci and
A. Restivo and
M. Sciortino Burrows--Wheeler transform and Sturmian
words . . . . . . . . . . . . . . . . . 241--246
Alexander Okhotin The hardest linear conjunctive language 247--253
Marc Chemillier and
Charlotte Truchet Computation of words satisfying the
``rhythmic oddity property'' (after
Simha Arom's works) . . . . . . . . . . 255--261
Shin-Shin Kao and
Lih-Hsing Hsu Brother trees: A family of optimal
$1_p$-Hamiltonian and $1$-edge
Hamiltonian graphs . . . . . . . . . . . 263--269
Chun-Nan Hung and
Hong-Chun Hsu and
Kao-Yung Liang and
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
M. Abellanas and
F. Hurtado and
V. Sacristán and
C. Icking and
L. Ma and
R. Klein and
E. Langetepe and
B. Palop Voronoi Diagram for services neighboring
a highway . . . . . . . . . . . . . . . 283--288
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Jer-Shyan Wu and
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
J. Sawada and
J. P. Spinrad From a simple elimination ordering to a
strong elimination ordering in linear
time . . . . . . . . . . . . . . . . . . 299--302
Brad Lushman and
Gordon V. Cormack Proof of correctness of Ressel's adOPTed
algorithm . . . . . . . . . . . . . . . 303--310
A. Hertz and
V. Lozin and
D. Schindl Finding augmenting chains in extensions
of claw-free graphs . . . . . . . . . . 311--316
Christian Igel and
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 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
Anonymous Subject Index ---- Volume 86 (2003) . . 343--344
Anonymous Author Index ---- Volume 86 (2003) . . . 345--347
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Uriel Feige and
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 and
Fabrizio Grandoni Detecting directed $4$-cycles still
faster . . . . . . . . . . . . . . . . . 13--15
Luca Aceto and
Wan Fokkink and
Anna Ingólfsdóttir A note on an expressiveness hierarchy
for multi-exit iteration . . . . . . . . 17--23
Beate Bollig and
Ingo Wegener Functions that have read-once branching
programs of quadratic size are not
necessarily testable . . . . . . . . . . 25--29
Jae-Hoon Kim and
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 and
Gerard J. Chang $k$-tuple domination in graphs . . . . . 45--50
Guillaume Fertin and
Emmanuel Godard and
André Raspaud Acyclic and $k$-distance coloring of the
grid . . . . . . . . . . . . . . . . . . 51--58
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Robert A. Hochberg and
Matthias F. 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 and
Tapio Elomaa and
Matti Kääriäinen Reduced Error Pruning of branching
programs cannot be approximated to
within a logarithmic factor . . . . . . 73--78
Harry Buhrman and
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 and
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 and
Jianbo Qian and
Zhongping Qin and
Binhai Zhu and
Robert Cimikowski A simple factor-3 approximation for
labeling points with circles . . . . . . 101--105
Tseng-Kuei Li and
Chang-Hsiung Tsai and
Jimmy J. M. Tan and
Lih-Hsing Hsu Bipanconnectivity and
edge-fault-tolerant bipancyclicity of
hypercubes . . . . . . . . . . . . . . . 107--110
Kazuyuki Amano and
Kazuo Iwama and
Akira Maruoka and
Kenshi Matsuo and
Akihiro Matsuura Inclusion--exclusion for $k$-CNF
formulas . . . . . . . . . . . . . . . . 111--117
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
M. Crochemore and
V. T. Stefanov Waiting time and complexity for matching
patterns with automata . . . . . . . . . 119--125
D. de Werra and
P. Hansen Using stable sets to bound the chromatic
number . . . . . . . . . . . . . . . . . 127--131
Sven Hartmann and
Anne Hoffmann and
Sebastian Link and
Klaus-Dieter Schewe Axiomatizing functional dependencies in
the Higher-Order Entity-Relationship
Model . . . . . . . . . . . . . . . . . 133--137
B. Litow Inequality of finite behaviors of
rational weight finite automata is in R 139--145
Michel Habib and
Emmanuelle Lebhar and
Christophe Paul A note on finding all homogeneous set
sandwiches . . . . . . . . . . . . . . . 147--151
B. S. Panda and
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 and
Shahrokh Saeednia Cryptanalysis of the Wu--Varadhrajan
fair exchange protocol . . . . . . . . . 169--171
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Jean Marcel Pallo Right-arm rotation distance between
binary trees . . . . . . . . . . . . . . 173--177
Xuehou Tan and
Tomio Hirata Finding shortest safari routes in simple
polygons . . . . . . . . . . . . . . . . 179--186
Jean H. Gallier and
Salvatore La Torre and
Supratik Mukhopadhyay Deterministic finite automata with
recursive calls and DPDAs . . . . . . . 187--193
L. Sunil Chandran and
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 and
Taisook Han A type system for the push-enter model 205--211
Wil Michiels and
Jan Korst Complexity of min--max subsequence
problems . . . . . . . . . . . . . . . . 213--217
Bernhard Fuchs A note on the terminal Steiner tree
problem . . . . . . . . . . . . . . . . 219--220
Ho-Sook Kim and
Hwan-Seung Yong Personalized cache management for mobile
computing environments . . . . . . . . . 221--228
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
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 and
David A. Rosenblueth Disjunctive partial deduction of a
right-to-left string-matching algorithm 235--241
Punit Chandra and
Ajay D. Kshemkalyani Distributed algorithm to detect strong
conjunctive predicates . . . . . . . . . 243--249
Stephen T. Hedetniemi and
David P. Jacobs and
Pradip K. Srimani Linear time self-stabilizing colorings 251--255
Yon Dohn Chung and
Jong Wook Kim and
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
SingLing Lee and
Hann-Jang Ho On minimizing the maximum congestion for
Weighted Hypergraph Embedding in a Cycle 271--275
Kilsoo Chun and
Seungjoo Kim and
Sangjin Lee and
Soo Hak Sung and
Seonhee Yoon Differential and linear cryptanalysis
for $2$-round SPNs . . . . . . . . . . . 277--282
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
B. Litow A note on commutative multivariate
rational series . . . . . . . . . . . . 283--285
Michael Hoffmann and
Csaba D. Tóth Alternating paths through disjoint line
segments . . . . . . . . . . . . . . . . 287--294
Juan Luis Esteban and
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 and
Holger Hermanns and
William H. Sanders Optimal state-space lumping in Markov
chains . . . . . . . . . . . . . . . . . 309--315
Ting-Yem Ho and
Jou-Ming Chang Sorting a sequence of strong kings in a
tournament . . . . . . . . . . . . . . . 317--320
Anna Gál and
Pavel Pudlák A note on monotone complexity and the
rank of matrices . . . . . . . . . . . . 321--326
B. Intrigila and
M. Nesi On structural properties of
eta-expansions of identity . . . . . . . 327--333
Anonymous Subject Index ---- Volume 87 (2003) . . 335--336
Anonymous Author Index ---- Volume 87 (2003) . . . 337--339
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
José Luiz Fiadeiro and
Jan Madey and
Andrzej Tarlecki Foreword . . . . . . . . . . . . . . . . 1--2
Jan Madey WMT----from a personal perspective . . . 3--6
W\ladys\law M. Turski It was fun . . . . . . . . . . . . . . . 7--12
Michael Jackson Why software writing is difficult and
will remain so . . . . . . . . . . . . . 13--25
Cliff B. Jones Operational semantics: Concepts and
their expression . . . . . . . . . . . . 27--32
Meir M. Lehman and
Juan F. Ramil Software evolution----Background,
theory, practice . . . . . . . . . . . . 33--44
Tom Maibaum On what exactly goes on when software is
developed step-by-step, II: The sequel 45--51
David Lorge Parnas Structured programming: A minor part of
software engineering . . . . . . . . . . 53--58
Michel Sintzoff On the design of correct and optimal
dynamical systems and games . . . . . . 59--65
Krzysztof Walczak and
Wojciech Cellary Modeling virtual worlds in databases . . 67--72
Józef Winkowski An algebraic characterization of
independence of Petri net processes . . 73--81
Niklaus Wirth Hardware/software co-design then and now 83--87
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Kiyoaki Yoshida and
Yasumasa Sujaku and
Tohru Kohda Number of mutual connections in
neighborhoods and its application to
self-diagnosable systems . . . . . . . . 89--94
Alexandros V. Gerbessiotis and
Constantinos J. Siniolakis Randomized selection in $n + C + o(n)$
comparisons . . . . . . . . . . . . . . 95--100
Petr Kolman A note on the greedy algorithm for the
unsplittable flow problem . . . . . . . 101--105
Noga Alon and
Oded Goldreich and
Yishay Mansour Almost $k$-wise independence versus
$k$-wise independence . . . . . . . . . 107--110
Thorsten Bernholt and
Roland Fried Computing the update of the repeated
median regression line in linear time 111--117
Marc Joye Cryptanalysis of a pay-as-you-watch
system . . . . . . . . . . . . . . . . . 119--120
Darin Goldstein Determination of the topology of a
directed network . . . . . . . . . . . . 121--131
Hasan Ural and
David Whittier Distributed testing without encountering
controllability and observability
problems . . . . . . . . . . . . . . . . 133--141
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Milind Dawande A notion of cross-perfect bipartite
graphs . . . . . . . . . . . . . . . . . 143--147
Ming-Chien Yang and
Tseng-Kuei Li and
Jimmy J. M. Tan and
Lih-Hsing Hsu Fault-tolerant cycle-embedding of
crossed cubes . . . . . . . . . . . . . 149--154
Giulia Galbiati On finding cycle bases and fundamental
cycle bases with a shortest maximal
cycle . . . . . . . . . . . . . . . . . 155--159
T. C. Edwin Cheng and
Zhaohui Liu $3/2$-approximation for two-machine
no-wait flowshop scheduling with
availability constraints . . . . . . . . 161--165
Vadim Lozin and
Dieter Rautenbach Some results on graphs without long
induced paths . . . . . . . . . . . . . 167--171
Yin-Te Tsai The constrained longest common
subsequence problem . . . . . . . . . . 173--176
Jean-Jacques Hébrard and
Bruno Zanuttini An efficient algorithm for Horn
description . . . . . . . . . . . . . . 177--182
Tzong-Sun Wu and
Chien-Lung Hsu and
Han-Yu Lin and
Po-Sheng Huang Improvement of the Miyazaki--Takaragi
threshold digital signature scheme . . . 183--186
Saurabh Srivastava and
R. K. Ghosh Distributed algorithms for finding and
maintaining a $k$-tree core in a dynamic
network . . . . . . . . . . . . . . . . 187--194
Jianjun Zhou and
Martin Müller Depth-First Discovery Algorithm for
incremental topological sorting of
directed acyclic graphs . . . . . . . . 195--200
Taekyoung Kwon Erratum to: ``Digital signature
algorithm for securing digital
identities'': [Inform. Process. Lett.
\bf 82 (2002) 247--252] . . . . . . . . 201--202
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Liang Chen and
Naoyuki Tokuda and
Akira Nagai A new differential LSI space-based
probabilistic document classifier . . . 203--212
Lars Kristiansen and
Paul J. Voda Complexity classes and fragments of C 213--218
Sándor P. Fekete and
Martin Skutella and
Gerhard J. Woeginger The complexity of economic equilibria
for house allocation markets . . . . . . 219--223
Wim H. Hesselink Salembier's Min-tree algorithm turned
into breadth first search . . . . . . . 225--229
Michael Okun and
Amnon Barak A new approach for approximating node
deletion problems . . . . . . . . . . . 231--236
Keren Horowitz and
Dahlia Malkhi Estimating network size from local
information . . . . . . . . . . . . . . 237--243
Cristian S. Calude and
Solomon Marcus and
Ludwig Staiger A topological characterization of random
sequences . . . . . . . . . . . . . . . 245--250
Sean Cleary and
Jennifer Taback Bounding restricted rotation distance 251--256
Anna Gál and
Pavel Pudlák Erratum to: ``A note on monotone
complexity and the rank of matrices'':
[Information Processing Letters \bf 87
(2003) 321--326] . . . . . . . . . . . . 257--257
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Gad M. Landau and
Baruch Schieber and
Michal Ziv-Ukelson Sparse LCS Common Substring Alignment 259--270
Jau-Der Shih A fault-tolerant wormhole routing scheme
for torus networks with nonconvex faults 271--278
Yong-Jin Choi and
Ho-Hyun Park and
Chin-Wan Chung Estimating the result size of a query to
velocity skewed moving objects . . . . . 279--285
Toru Araki Edge-pancyclicity of recursive
circulants . . . . . . . . . . . . . . . 287--292
Seong-Hun Paeng On the security of cryptosystem using
automorphism groups . . . . . . . . . . 293--298
Pantelimon St\uanic\ua and
Subhamoy Maitra A constructive count of rotation
symmetric functions . . . . . . . . . . 299--304
Jean-Marie Vanherpe Some optimization problems on
weak-bisplit graphs . . . . . . . . . . 305--310
Anonymous Subject Index ---- Volume 88 (2003) . . 311--312
Anonymous Author Index ---- Volume 88 (2003) . . . 313--314
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Ruggero Lanotte and
Andrea Maggiolo-Schettini and
Simone Tini $\epsilon$-transitions in Concurrent
Timed Automata . . . . . . . . . . . . . 1--7
Iiro Honkala and
Tero Laihonen On identifying codes in the hexagonal
mesh . . . . . . . . . . . . . . . . . . 9--14
Doratha E. Drake and
Stefan Hougardy On approximation algorithms for the
terminal Steiner tree problem . . . . . 15--18
Timothy M. Chan A note on maximum independent sets in
rectangle intersection graphs . . . . . 19--23
Millist W. Vincent and
Jixue Liu Irrelevant updates and
self-maintainability in transitive
closure database views . . . . . . . . . 25--29
Floris Geerts and
Bart Kuijpers Topological formulation of termination
properties of iterates of functions . . 31--35
Gunter Grieser and
Steffen Lange Incremental learning of approximations
from positive data . . . . . . . . . . . 37--42
N. V. Vinodchandran $\mbox{AM}_{\mbox{exp}} \not \subseteq
(\mbox{NP} \cap
\mbox{coNP})/\mbox{poly}$ . . . . . . . 43--47
Bruce K. Durgan Compact searchable static binary trees 49--52
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Suzanne M. Seager The greedy algorithm for domination in
graphs of maximum degree $3$ . . . . . . 53--56
Rudolf Fleischer and
Mordecai Golin and
Chin-Tau Lea and
Steven Wong Finding optimal paths in MREP routing 57--63
Wojciech Fraczak and
Anna Podolak A characterization of $s$-languages . . 65--70
Stasys Jukna On the minimum number of negations
leading to super-polynomial savings . . 71--74
Ralf Klasing and
Christian Laforest Hardness results and approximation
algorithms of $k$-tuple domination in
graphs . . . . . . . . . . . . . . . . . 75--83
Dániel Marx List edge multicoloring in graphs with
few cycles . . . . . . . . . . . . . . . 85--90
Sasanka Roy and
Partha P. Goswami and
Sandip Das and
Subhas C. Nandy Optimal algorithm for a special
point-labeling problem . . . . . . . . . 91--98
Paul Valiant The Log-Rank Conjecture and low degree
polynomials . . . . . . . . . . . . . . 99--103
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
L. Sunil Chandran Minimum cuts, girth and a spectral
threshold . . . . . . . . . . . . . . . 105--110
F. Hess On the security of the
verifiably-encrypted signature scheme of
Boneh, Gentry, Lynn and Shacham . . . . 111--114
Joo-Won Jung and
Kyung-Yong Chwa Labeling points with given rectangles 115--121
Christel Baier and
Holger Hermanns and
Joost-Pieter Katoen Probabilistic weak simulation is
decidable in polynomial time . . . . . . 123--130
I. Kerenidis and
A. Nayak Weak coin flipping with small bias . . . 131--135
Boaz Ben-Moshe and
Paz Carmi and
Matthew J. Katz Computing all large sums-of-pairs in
$\mathbb{R}^n$ and the discrete planar
two-watchtower problem . . . . . . . . . 137--139
Thomas Perst and
Helmut Seidl Macro forest transducers . . . . . . . . 141--149
Guilherme D. da Fonseca and
Celina M. H. de Figueiredo and
Paulo C. P. Carvalho Kinetic hanger . . . . . . . . . . . . . 151--157
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Manoel Campêlo and
Ricardo Corrêa and
Yuri Frota Cliques, holes and the vertex coloring
polytope . . . . . . . . . . . . . . . . 159--164
Andreas Brandstädt and
Van Bang Le and
H. N. de Ridder Efficient robust algorithms for the
Maximum Weight Stable Set Problem in
chair-free graph classes . . . . . . . . 165--173
Pilu Crescenzi and
Federico Greco The minimum likely column cover problem 175--179
András Kovács and
Tamás Kis Partitioning of trees for minimizing
height and cardinality . . . . . . . . . 181--185
L. F. Johnson Tumble, a fast simple iteration
algorithm for Fibonacci . . . . . . . . 187--189
Salvador Lucas Strong and NV-sequentiality of
constructor systems . . . . . . . . . . 191--201
Fu-Hsing Wang and
Yue-Li Wang and
Jou-Ming Chang Feedback vertex sets in star graphs . . 203--208
Ciprian Doru Giurc\uaneanu On some properties of the NML estimator
for Bernoulli strings . . . . . . . . . 209--213
Anonymous Board of Editors . . . . . . . . . . . . CO2--CO2
Bruno Codenotti and
Gianluca De Marcoo and
Mauro Leoncini and
Manuela Montangero and
Massimo Santini Approximation algorithms for a
hierarchically structured bin packing
problem . . . . . . . . . . . . . . . . 215--221
Hiroshi Nagamochi and
Takahisa Suzuki and
Toshimasa Ishii A simple recognition of maximal planar
graphs . . . . . . . . . . . . . . . . . 223--226
Guilin Wang Universal forgery on a group signature
scheme using self-certified public keys 227--231
Vladlen Koltun Ready, Set, Go! The Voronoi diagram of
moving points that start from a line . . 233--235
Jérôme Durand-Lose A Kleene theorem for splitable signals 237--245
Irit Dinur and
Shmuel Safra On the hardness of approximating
label-cover . . . . . . . . . . . . . . 247--254
Elias Dahlhaus and
Peter Dankelmann and
R. Ravi A linear-time algorithm to compute a MAD
tree of an interval graph . . . . . . . 255--259
Harald Fecher A completed hierarchy of true concurrent
equivalences . . . . . . . . . . . . . . 261--265
Anonymous Board of Editors . . . . . . . . . . . . ??
Hendrik Jan Hoogeboom and
Walter A. Kosters Tetris and decidability . . . . . . . . 267--272
Nikolaos Laoutaris and
Vassilios Zissimopoulos and
Ioannis Stavrakakis Joint object placement and node
dimensioning for Internet content
distribution . . . . . . . . . . . . . . 273--279
Mayer Goldberg A construction of one-point bases in
extended lambda calculi . . . . . . . . 281--286
Yung-Ling Lai and
Gerard J. Chang On the profile of the corona of two
graphs . . . . . . . . . . . . . . . . . 287--292
Hemangee K. Kapoor and
Mark B. Josephs Modelling and verification of
delay-insensitive circuits using CCS and
the Concurrency Workbench . . . . . . . 293--296
Maciej Li\'skiewicz and
Bodo Manthey New lower and upper bounds for the
competitive ratio of transmission
protocols . . . . . . . . . . . . . . . 297--301
Laurent Alonso and
Philippe Chassaing and
Edward M. Reingold and
René Schott The worst-case chip problem . . . . . . 303--308
Tetsuo Yokoyama and
Zhenjiang Hu and
Masato Takeichi Deterministic second-order patterns . . 309--314
Anonymous Subject Index --- Volume 89 (2004) . . . 315--316
Anonymous Board of Editors . . . . . . . . . . . . ??
Andrzej Tarlecki Editorial . . . . . . . . . . . . . . . 1--2
N. Markey and
Ph. Schnoebelen A PTIME-complete matching problem for
SLP-compressed words . . . . . . . . . . 3--6
N. Lesh and
J. Marks and
A. McMahon and
M. Mitzenmacher Exhaustive approaches to $2$D
rectangular perfect packings . . . . . . 7--14
Shao Chin Sung and
Keisuke Tanaka Limiting negations in bounded-depth
circuits: An extension of Markov's
theorem . . . . . . . . . . . . . . . . 15--20
Stavros Tripakis Undecidable problems of decentralized
observation and control on regular
languages . . . . . . . . . . . . . . . 21--28
R\uazvan Diaconescu Herbrand theorems in arbitrary
institutions . . . . . . . . . . . . . . 29--37
Roy Friedman and
Achour Mostefaoui and
Michel Raynal A weakest failure detector-based
asynchronous consensus protocol for $f <
n$ . . . . . . . . . . . . . . . . . . . 39--46
Mahesh Kallahalla and
Peter J. Varman Analysis of simple randomized buffer
management for parallel I/O . . . . . . 47--52
Anonymous Board of Editors . . . . . . . . . . . . ??
Vicent Cholvi and
Josep Bernabéu Relationships between memory models . . 53--58
Toshihiro Fujito and
Takashi Doi A 2-approximation NC algorithm for
connected vertex cover and tree cover 59--63
Ioannis N. Kouris and
Christos H. Makris and
Athanasios K. Tsakalidis Efficient automatic discovery of `hot'
itemsets . . . . . . . . . . . . . . . . 65--72
Abdullah AlWehaibi and
Michael Kadoch and
Anjali Agarwal and
Ahmed ElHakeem Packet loss probability for DiffServ
over IP and MPLS reliable homogeneous
multicast networks . . . . . . . . . . . 73--80
Hongfei Sui and
Jianxin Wang and
Jianer Chen and
Songqiao Chen The cost of becoming anonymous: on the
participant payload in Crowds . . . . . 81--86
Eurípides Montagne and
Anand Ekambaram An optimal storage format for sparse
matrices . . . . . . . . . . . . . . . . 87--92
Ding Liu A note on point location in arrangements
of hyperplanes . . . . . . . . . . . . . 93--95
Emilio Di Giacomo and
Giuseppe Liotta and
Maurizio Patrignani A note on $3$D orthogonal drawings with
direction constrained edges . . . . . . 97--101
Anonymous Board of Editors . . . . . . . . . . . . ??
A. Savelli On numerically decipherable codes and
their homophonic partitions . . . . . . 103--108
Iordanis Kerenidis and
Ronald de Wolf Quantum symmetrically-private
information retrieval . . . . . . . . . 109--114
Kazuo Iwama and
Kouki Yonezawa The orthogonal CNN problem . . . . . . . 115--120
Evangelos Kranakis and
Danny Krizanc and
Sunil Shende Approximate hotlink assignment . . . . . 121--128
Joan M. Lucas A direct algorithm for restricted
rotation distance . . . . . . . . . . . 129--134
Gabriel Nivasch Cycle detection using a stack . . . . . 135--140
Sergey Bereg Transforming pseudo-triangulations . . . 141--145
Jin-Yi Cai and
Osamu Watanabe Relativized collapsing between BPP and
PH under stringent oracle access . . . . 147--154
Yih-Ching Su and
Chu-Sing Yang and
Chen-Wei Lee The analysis of packet loss prediction
for Gilbert-model with loss rate uplink 155--159
Anonymous Board of Editors . . . . . . . . . . . . ??
Ernst-Erich Doberkat Factoring stochastic relations . . . . . 161--166
Valerio Freschi and
Alessandro Bogliolo Longest common subsequence between
run-length-encoded strings: a new
algorithm with improved parallelism . . 167--173
Francis Y. L. Chin and
Alfredo De Santis and
Anna Lisa Ferrara and
N. L. Ho and
S. K. Kim A simple algorithm for the constrained
sequence problems . . . . . . . . . . . 175--179
James F. Korsh and
Paul S. LaFollette Constant time generation of derangements 181--186
Alexandros V. Gerbessiotis and
Constantinos J. Siniolakis Probabilistic integer sorting . . . . . 187--193
Harumichi Nishimura and
Tomoyuki Yamakami Polynomial time quantum computation with
advice . . . . . . . . . . . . . . . . . 195--204
Nicholas J. A. Harvey and
J. Ian Munro Deterministic SkipNet . . . . . . . . . 205--208
Guy Melançon and
Fabrice Philippe Generating connected acyclic digraphs
uniformly at random . . . . . . . . . . 209--213
Anonymous Board of Editors . . . . . . . . . . . . ??
Jean-Loup Guillaume and
Matthieu Latapy Bipartite structure of all complex
networks . . . . . . . . . . . . . . . . 215--221
Mads Sig Ager and
Olivier Danvy and
Jan Midtgaard A functional correspondence between
call-by-need evaluators and lazy
abstract machines . . . . . . . . . . . 223--232
David P. Bunde SPT is optimally competitive for
uniprocessor flow . . . . . . . . . . . 233--238
Petra \vSparl and
Janez \vZerovnik $2$-local $5/4$-competitive algorithm
for multicoloring triangle-free
hexagonal graphs . . . . . . . . . . . . 239--246
Richard Parker and
Andrew Plater Addition chains with a bounded number of
registers . . . . . . . . . . . . . . . 247--252
Sang-Wook Kim and
Dae-Hyun Park and
Heon-Gil Lee Efficient processing of subsequence
matching with the Euclidean metric in
time-series databases . . . . . . . . . 253--260
C. \`Alvarez and
M. Blesa and
J. Díaz and
A. Fernández and
M. Serna The complexity of deciding stability
under FFS in the Adversarial Queueing
model . . . . . . . . . . . . . . . . . 261--266
Mark Weston A fixed-parameter tractable algorithm
for matrix domination . . . . . . . . . 267--272
Anonymous Board of Editors . . . . . . . . . . . . ??
J. Breit An improved approximation algorithm for
two-machine flow shop scheduling with an
availability constraint . . . . . . . . 273--278
Maw-Shang Chang and
Chin-Hua Lin and
Chuan-Min Lee New upper bounds on feedback vertex
numbers in butterflies . . . . . . . . . 279--285
R. M. Hierons Using a minimal number of resets when
testing from a finite state machine . . 287--292
Mingjun Ji and
Huanwen Tang and
Juan Guo A single-point mutation evolutionary
programming . . . . . . . . . . . . . . 293--299
Hana Chockler and
Dan Gutfreund A lower bound for testing juntas . . . . 301--305
S. D. Nikolopoulos and
C. Nomikos and
P. Rondogiannis A limit characterization for the number
of spanning trees of graphs . . . . . . 307--313
Anonymous Author Index --- Volume 90 (2004) . . . 315--316
Anonymous Master Subject Index --- Volumes 81--90 317--318
Anonymous Master Index --- Volumes 81--90 . . . . 319--330
Petteri Kaski Packing Steiner trees with identical
terminal sets . . . . . . . . . . . . . 1--5
Angelika Hellwig and
Dieter Rautenbach and
Lutz Volkmann Note on the connectivity of line graphs 7--10
Chong-Dae Park and
Kyung-Yong Chwa Hamiltonian properties on the class of
hypercube-like networks . . . . . . . . 11--17
Alexander Gaysinsky and
Alon Itai and
Hadas Shachnai Strongly competitive algorithms for
caching with pipelined prefetching . . . 19--27
Willi Geiselmann and
Rainer Steinwandt Power attacks on a side-channel
resistant elliptic curve implementation 29--32
Raphael C.-W. Phan Impossible differential cryptanalysis of
7-round Advanced Encryption Standard
(AES) . . . . . . . . . . . . . . . . . 33--38
D. R. Stinson Attack on a concast signature scheme . . 39--41
Mark Ettinger and
Peter Hòyer and
Emanuel Knill The quantum query complexity of the
hidden subgroup problem is polynomial 43--48
Ying Li and
Yibin Hou Search audio data with the wavelet
pyramidal algorithm . . . . . . . . . . 49--55
Anonymous Board of Editors . . . . . . . . . . . . ??
Zoltán Fülöp and
Armin Kühnemann and
Heiko Vogler A bottom-up characterization of
deterministic top-down tree transducers
with regular look-ahead . . . . . . . . 57--67
Jongik Kim and
Sang Ho Lee and
Hyoung-Joo Kim Efficient structural joins with
clustered extents . . . . . . . . . . . 69--75
Zhengnan Shi and
Wayne Goddard and
Stephen T. Hedetniemi An anonymous self-stabilizing algorithm
for 1-maximal independent set in trees 77--83
Masataka Takamura and
Tom Altman and
Yoshihide Igarashi Speedup of Vidyasankar's algorithm for
the group $k$-exclusion problem . . . . 85--91
Dirk Leinders and
Jerzy Tyszkiewicz and
Jan Van den Bussche On the expressive power of semijoin
queries . . . . . . . . . . . . . . . . 93--98
Jop F. Sibeyn External matrix multiplication and
all-pairs shortest path . . . . . . . . 99--106
Anonymous Board of Editors . . . . . . . . . . . . ??
Krishna Kumaraswamy and
Vasileios Megalooikonomou and
Christos Faloutsos Fractal dimension and vector
quantization . . . . . . . . . . . . . . 107--113
Sung-Ryul Kim and
Inbok Lee and
Kunsoo Park A fast algorithm for the generalized
$k$-keyword proximity problem given
keyword offsets . . . . . . . . . . . . 115--120
Giacomo Lenzi and
Erich Monteleone On Fixpoint Arithmetic and Infinite Time
Turing Machines . . . . . . . . . . . . 121--128
Wing-Kai Hon and
Ming-Yang Kao and
Tak-Wah Lam and
Wing-Kin Sung and
Siu-Ming Yiu Non-shared edges and nearest neighbor
interchanges revisited . . . . . . . . . 129--134
Seung-Joon Oh and
Jae-Yearn Kim A hierarchical clustering algorithm for
categorical sequence data . . . . . . . 135--140
Jakob Grue Simonsen On confluence and residuals in Cauchy
convergent transfinite rewriting . . . . 141--146
Y. H. Tsin On finding an ear decomposition of an
undirected graph distributively . . . . 147--153
Anonymous Board of Editors . . . . . . . . . . . . ??
Anonymous Harald Ganzinger . . . . . . . . . . . . 155--155
Jan Poland A coding theorem for Enumerable Output
Machines . . . . . . . . . . . . . . . . 157--161
Pradipta Prometheus Mitra and
Muhammad Arshad Ul Abedin and
Md. Abul Kashem Algorithms for solving the symmetry
number problem on trees . . . . . . . . 163--169
Ramtin Khosravi and
Mohammad Ghodsi Shortest paths in simple polygons with
polygon-meet constraints . . . . . . . . 171--176
Jan Remy Resource constrained scheduling on
multiple machines . . . . . . . . . . . 177--182
Raja Jothi and
Balaji Raghavachari Survivable network design: the
capacitated minimum spanning network
problem . . . . . . . . . . . . . . . . 183--190
Fangguo Zhang and
Xiaofeng Chen Attack on an ID-based authenticated
group key agreement scheme from PKC 2004 191--193
Partha Dutta and
Rachid Guerraoui and
Bastian Pochon Fast non-blocking atomic commit: an
inherent trade-off . . . . . . . . . . . 195--200
Anonymous Board of Editors . . . . . . . . . . . . ??
Krishnendu Chatterjee and
Pallab Dasgupta and
P. P. Chakrabarti The power of first-order quantification
over states in branching and linear time
temporal logics . . . . . . . . . . . . 201--210
Ye Jun and
Liu Xiande and
Han Lu Evolutionary game algorithm for
continuous parameter optimization . . . 211--219
Hiroshi Nagamochi and
Nobuyasu Yamada Counting edge crossings in a 2-layered
drawing . . . . . . . . . . . . . . . . 221--225
Yong H. Shin and
Hyokyung Bahn A scalable Web cache sharing scheme . . 227--232
Markus Müller-Olm and
Helmut Seidl Computing polynomial program invariants 233--244
YijieHan Improved algorithm for all pairs
shortest paths . . . . . . . . . . . . . 245--250
Anonymous Board of Editors . . . . . . . . . . . . ??
Ralf Hartmut Güting and
Zhiming Ding A simple but effective improvement to
the plumb-line algorithm . . . . . . . . 251--257
Rainer E. Burkard and
Vladimir G. Deineko On the Euclidean TSP with a permuted Van
der Veen matrix . . . . . . . . . . . . 259--262
Bruno Durand and
Nikolai Vereshchagin Kolmogorov--Loveland stochasticity for
finite strings . . . . . . . . . . . . . 263--269
Seth Pettie and
Peter Sanders A simpler linear time $2/3 - \epsilon$
approximation for maximum weight
matching . . . . . . . . . . . . . . . . 271--276
Miklós Bartha and
Miklós Krész Tutte type theorems for graphs having a
perfect internal matching . . . . . . . 277--284
Steffen Lange and
Sandra Zilles Formal language identification: query
learning vs. Gold-style learning . . . . 285--292
Chang-Hsiung Tsai and
Jimmy J. M. Tan and
Lih-Hsing Hsu The super-connected property of
recursive circulant graphs . . . . . . . 293--298
Ilyong Chung Erratum to: ``The design of conference
key distribution system employing a
symmetric balanced incomplete block
design'': [Inform. Process. Lett. 81
(2002) 313--318] . . . . . . . . . . . . 299--300
Anonymous Subject Index --- Volume 91 (2004) . . . 301--302
Anonymous Board of Editors . . . . . . . . . . . . ??
Masafumi Yamashita and
Ichiro Suzuki and
Tiko Kameda Searching a polygonal region by a group
of stationary $k$-searchers . . . . . . 1--8
Gabriel Valiente Trading uninitialized space for time . . 9--13
Chung-Haw Chang and
Cheng-Kuan Lin and
Hua-Min Huang and
Lih-Hsing Hsu The super laceability of the hypercubes 15--21
Ding Liu A strong lower bound for approximate
nearest neighbor searching . . . . . . . 23--29
Xiaofan Yang and
David J. Evans and
Hongjian Lai and
Graham M. Megson Generalized honeycomb torus is
Hamiltonian . . . . . . . . . . . . . . 31--37
B. Litow and
N. Deo Graph compression and the zeros of
polynomials . . . . . . . . . . . . . . 39--44
Byron L. D. Bezerra and
Francisco de A. T. de Carvalho A symbolic approach for content-based
information filtering . . . . . . . . . 45--52
S. A. Curtis Darts and hoopla board design . . . . . 53--56
Anonymous Board of Editors . . . . . . . . . . . . ??
Atsuko Yamaguchi and
Kiyoko F. Aoki and
Hiroshi Mamitsuka Finding the maximum common subgraph of a
partial $k$-tree and a graph with a
polynomially bounded number of spanning
trees . . . . . . . . . . . . . . . . . 57--63
Andrzej Szepietowski and
Monika Targan A note on the oriented chromatic number
of grids . . . . . . . . . . . . . . . . 65--70
Pascal Ochem Oriented colorings of triangle-free
planar graphs . . . . . . . . . . . . . 71--76
S. Fossé and
G. Richomme Some characterizations of Parikh matrix
equivalent binary words . . . . . . . . 77--82
Hagen Völzer A constructive proof for FLP . . . . . . 83--87
G. Ausiello and
M. Demange and
L. Laura and
V. Paschos Algorithms for the On-Line Quota
Traveling Salesman Problem . . . . . . . 89--94
Maciej Kurowski A $1.235$ lower bound on the number of
points needed to draw all $n$-vertex
planar graphs . . . . . . . . . . . . . 95--98
Heum-Geun Kang and
Jun-Ki Min and
Seok-Ju Chun and
Chin-Wan Chung A compression method for prefix-sum
cubes . . . . . . . . . . . . . . . . . 99--105
Anonymous Board of Editors . . . . . . . . . . . . ??
Garth Isaak and
Darren A. Narayan A classification of tournaments having
an acyclic tournament as a minimum
feedback arc set . . . . . . . . . . . . 107--111
Benjamin Doerr Global roundings of sequences . . . . . 113--116
I. Krasikov and
S. D. Noble Finding next-to-shortest paths in a
graph . . . . . . . . . . . . . . . . . 117--119
Alok Aggarwal and
Youngcheul Wee On the symmetric angle-restricted
nearest neighbor problem . . . . . . . . 121--126
Jin-Yi Cai and
Robert A. Threlfall A note on quadratic residuosity and UP 127--131
Jeong Min Shim and
Seok Il Song and
Jae Soo Yoo and
Young Soo Min An efficient cache conscious
multi-dimensional index structure . . . 133--142
Igor E. Shparlinski On the uniformity of distribution of the
decryption exponent in fixed encryption
exponent RSA . . . . . . . . . . . . . . 143--147
Ismail H. Toroslu and
Ahmet Cosar Dynamic programming solution for
multiple query optimization problem . . 149--155
George Davie Characterising the Martin-Löf random
sequences using computably enumerable
sets of measure one . . . . . . . . . . 157--160
Anonymous Board of Editors . . . . . . . . . . . . ??
San Skulrattanakulchai Acyclic colorings of subcubic graphs . . 161--167
Jens Lechtenbörger Computing unique canonical covers for
simple FDs via transitive reduction . . 169--174
Irit Katriel On the algebraic complexity of set
equality and inclusion . . . . . . . . . 175--178
Md. Abul Kashem and
M. Ziaur Rahman An optimal parallel algorithm for
$c$-vertex-ranking of trees . . . . . . 179--184
Aaron Windsor A simple proof that finding a maximal
independent set in a graph is in NC . . 185--187
Soumen Maity and
Amiya Nayak and
Bimal K. Roy Characterization of catastrophic faults
in two-dimensional reconfigurable
systolic arrays with unidirectional
links . . . . . . . . . . . . . . . . . 189--197
Alfredo De Santis and
Anna Lisa Ferrara and
Barbara Masucci Cryptographic key assignment schemes for
any access control policy . . . . . . . 199--205
Lars Engebretsen Simplified tight analysis of Johnson's
algorithm . . . . . . . . . . . . . . . 207--210
Anonymous Board of Editors . . . . . . . . . . . . ??
Tatjana Petkovi\'c and
Miroslav \'Ciri\'c and
Stojan Bogdanovi\'c Minimal forbidden subwords . . . . . . . 211--218
Donglei Du Optimal preemptive semi-online
scheduling on two uniform processors . . 219--223
E. Bertsch and
M.-J. Nederhof Fast parallel recognition of LR language
suffixes . . . . . . . . . . . . . . . . 225--229
Ku-Young Chang and
Howon Kim and
Ju-Sung Kang and
Hyun-Sook Cho An extension of TYT algorithm for
$\mathrm{GF}((2^n)^m)$ using
precomputation . . . . . . . . . . . . . 231--234
Jack H. Lutz Computability versus exact computability
of martingales . . . . . . . . . . . . . 235--237
K. S. Cheung New characterization for live and
reversible augmented marked graphs . . . 239--243
Amit Weisman and
L. Paul Chew and
Klara Kedem Voronoi diagrams of moving points in the
plane and of lines in space: tight
bounds for simple configurations . . . . 245--251
Owen Kaser Compressing arrays by ordering attribute
values . . . . . . . . . . . . . . . . . 253--256
Eyas El-Qawasmeh Word prediction using a clustered
optimal binary search tree . . . . . . . 257--265
Anonymous Board of Editors . . . . . . . . . . . . ??
Cezar Câmpeanu and
Sheng Yu Pattern expressions and pattern automata 267--274
Daniel J. Dougherty and
Stanley M. Selkow The complexity of the certification of
properties of Stable Marriage . . . . . 275--277
I. Nunes Method redefinition---ensuring
alternative behaviors . . . . . . . . . 279--285
John Hershberger Kinetic collision detection with fast
flight plan changes . . . . . . . . . . 287--291
Ayelet Butman and
Revital Eres and
Gad M. Landau Scaled and permuted string matching . . 293--297
Yu-Wei Chen An enhanced recursive frequency
splitting broadcasting algorithm for
near video-on-demand services . . . . . 299--302
Bang Ye Wu and
Zheng-Nan Huang and
Fu-Jie Zhan Exact algorithms for the minimum latency
problem . . . . . . . . . . . . . . . . 303--309
Kuen-Fang Jea and
Ming-Yuan Chang and
Ke-Chung Lin An efficient and flexible algorithm for
online mining of large itemsets . . . . 311--316
Anonymous Subject Index --- Volume 92 (2004) . . . 317--318
Anonymous Board of Editors . . . . . . . . . . . . ??
Tee Connie and
Andrew Teoh and
Michael Goh and
David Ngo PalmHashing: a novel approach for
cancelable biometrics . . . . . . . . . 1--5
Daiji Fukagawa and
Tatsuya Akutsu Performance analysis of a greedy
algorithm for inferring Boolean
functions . . . . . . . . . . . . . . . 7--12
Haim Kaplan and
Nira Shafrir The greedy algorithm for shortest
superstrings . . . . . . . . . . . . . . 13--17
Fengfeng Zhou and
Yinlong Xu and
Guoliang Chen No-wait scheduling in single-hop
multi-channel LANs . . . . . . . . . . . 19--24
Michaël Quisquater and
Bart Preneel and
Joos Vandewalle Spectral characterization of
cryptographic Boolean functions
satisfying the (extended) propagation
criterion of degree $l$ and order $k$ 25--28
Jun Zheng and
Shahram Latifi and
Emma Regentova and
Kai Luo and
Xiaolong Wu Diagnosability of star graphs under the
comparison diagnosis model . . . . . . . 29--36
Sheng Zhou and
Christopher B. Jones HCPO: an efficient insertion order for
incremental Delaunay triangulation . . . 37--42
Daewan Han and
Moonsik Lee An algebraic attack on the improved
summation generator with 2-bit memory 43--46
R. Durán Díaz and
J. Muñoz Masqué Optimal strong primes . . . . . . . . . 47--52
Anonymous Board of Editors . . . . . . . . . . . . ??
Mitre C. Dourado and
Fábio Protti and
Jayme L. Szwarcfiter The Helly property on subfamilies of
limited size . . . . . . . . . . . . . . 53--56
A. Noore and
P. L. Cross Modeling the reliability of large
dynamic distributed non-homogeneous
networks . . . . . . . . . . . . . . . . 57--61
Haejae Jung The $d$-deap*: a fast and simple
cache-aligned $d$-ary deap . . . . . . . 63--67
Steffen Heber and
Carla D. Savage Common intervals of trees . . . . . . . 69--74
Celina M. H. de Figueiredo and
Vinícius G. P. de Sá Note on the Homogeneous Set Sandwich
Problem . . . . . . . . . . . . . . . . 75--81
Gill Barequet and
Gershon Elber Optimal bounding cones of vectors in
three dimensions . . . . . . . . . . . . 83--89
Angeline Wong and
Leejay Wu and
Phillip B. Gibbons and
Christos Faloutsos Fast estimation of fractal dimension and
correlation integral on stream data . . 91--97
Jun-Jie Pan and
Gerard J. Chang Isometric-path numbers of block graphs 99--102
Anonymous Board of Editors . . . . . . . . . . . . ??
Akio Fujiyoshi Linearity and nondeletion on monadic
context-free tree grammars . . . . . . . 103--107
Andrzej Pelc and
David Peleg Broadcasting with locally bounded
Byzantine faults . . . . . . . . . . . . 109--115
Mirtha-Lina Fernández Relaxing monotonicity for innermost
termination . . . . . . . . . . . . . . 117--123
L. Sunil Chandran and
Fabrizio Grandoni Refined memorization for vertex cover 125--131
Jianxi Fan and
Xiaola Lin and
Xiaohua Jia Node-pancyclicity and edge-pancyclicity
of crossed cubes . . . . . . . . . . . . 133--138
Jouni K. Seppänen Upper bound for the approximation ratio
of a class of hypercube segmentation
algorithms . . . . . . . . . . . . . . . 139--141
Sudip Seal and
Srikanth Komarina and
Srinivas Aluru An optimal hierarchical clustering
algorithm for gene expression data . . . 143--147
Ludwig Staiger Constructive dimension equals Kolmogorov
complexity . . . . . . . . . . . . . . . 149--153
Anonymous Board of Editors . . . . . . . . . . . . ??
Mirtha-Lina Fernández On proving $C_E$-termination of
rewriting by size-change termination . . 155--162
Alexander Thomasian Reconstruct versus read-modify writes in
RAID . . . . . . . . . . . . . . . . . . 163--168
Andrzej Lingas and
Martin Wahlen A note on maximum independent set and
related problems on box graphs . . . . . 169--171
Minghui Jiang UPS-$k$ : a set partitioning problem
with applications in UPS pickup-delivery
system . . . . . . . . . . . . . . . . . 173--175
Jun-Ho Her and
R. S. Ramakrishna External-memory depth-first search
algorithm for solid grid graphs . . . . 177--183
Nathan Segerlind Exponential separation between
$\mathrm{Res}(k)$ and $\mathrm{Res}(k +
1)$ for $k \leq \epsilon \log n$ . . . . 185--190
Mingyan Li and
Radha Poovendran and
David A. McGrew Minimizing center key storage in hybrid
one-way function based group key
management with communication
constraints . . . . . . . . . . . . . . 191--198
Stelvio Cimato and
Alfredo De Santis and
Anna Lisa Ferrara and
Barbara Masucci Ideal contrast visual cryptography
schemes with reversing . . . . . . . . . 199--206
Anonymous Board of Editors . . . . . . . . . . . . ??
Sandeep S. Kulkarni and
Chase Bolen and
John Oleszkiewicz and
Andrew Robinson Alternators in read/write atomicity . . 207--215
MohammadReza Mousavi and
Michel Reniers and
Jan Friso Groote A syntactic commutativity format for SOS 217--223
Franck Leprévost and
Jean Monnerat and
Sébastien Varrette and
Serge Vaudenay Generating anomalous elliptic curves . . 225--230
Hiroshi Nagamochi On computing minimum $(s, t)$-cuts in
digraphs . . . . . . . . . . . . . . . . 231--237
Frédéric Chataigner Approximating the Maximum Agreement
Forest on $k$ trees . . . . . . . . . . 239--244
Min Xu and
Jun-Ming Xu and
Xin-Min Hou Fault diameter of Cartesian product
graphs . . . . . . . . . . . . . . . . . 245--248
I-Hsuan Yang and
Chien-Pin Huang and
Kun-Mao Chao A fast algorithm for computing a longest
common increasing subsequence . . . . . 249--253
X. H. Shi and
Y. C. Liang and
H. P. Lee and
C. Lu and
L. M. Wang An improved GA and a novel PSO-GA-based
hybrid algorithm . . . . . . . . . . . . 255--261
Anonymous Board of Editors . . . . . . . . . . . . ??
Frank Nielsen and
Richard Nock A fast deterministic smallest enclosing
disk approximation algorithm . . . . . . 263--268
Ryoichi Kato and
Osamu Watanabe Substring search and repeat search using
factor oracles . . . . . . . . . . . . . 269--274
Sung Kwon Kim Finding a longest nonnegative path in a
constant degree tree . . . . . . . . . . 275--279
K. Rustan M. Leino Efficient weakest preconditions . . . . 281--288
S. B. Fröschle The decidability border of hereditary
history preserving bisimilarity . . . . 289--293
Ruy Fabila Monroy and
J. Urrutia Graham triangulations and triangulations
with a center are Hamiltonian . . . . . 295--299
M. Kano and
C. Merino and
J. Urrutia On plane spanning trees and cycles of
multicolored point sets with few
intersections . . . . . . . . . . . . . 301--306
Thierry Garcia and
David Semé A Coarse-Grained Multicomputer algorithm
for the detection of repetitions . . . . 307--313
Anonymous Subject Index --- Volume 93 (2005) . . . 315--316
Anonymous Board of Editors . . . . . . . . . . . . ??
Janja Jerebic and
Sandi Klav\vzar and
Simon \vSpacapan Characterizing $r$-perfect codes in
direct products of two and three cycles 1--6
Ioannis Koutis A faster parameterized algorithm for set
packing . . . . . . . . . . . . . . . . 7--9
Róbert Lórencz and
Josef Hlavá\vc Subtraction-free Almost Montgomery
Inverse algorithm . . . . . . . . . . . 11--14
Stavros G. Kolliopoulos Minimum-cost single-source 2-splittable
flow . . . . . . . . . . . . . . . . . . 15--18
Eric Angel and
Evripidis Bampis and
Laurent Gourv\`es Approximation results for a bicriteria
job scheduling problem on a single
machine without preemption . . . . . . . 19--27
F. Carrabs and
R. Cerulli and
M. Gentili and
G. Parlato A linear time algorithm for the minimum
Weighted Feedback Vertex Set on diamonds 29--35
M. Sohel Rahman and
M. Kaykobad On Hamiltonian cycles and Hamiltonian
paths . . . . . . . . . . . . . . . . . 37--41
Sanguthevar Rajasekaran and
Sandeep Sen A generalization of the 0--1 principle
for sorting . . . . . . . . . . . . . . 43--47
Anonymous Board of Editors . . . . . . . . . . . . ??
Artur Czumaj and
Magnús M. Halldórsson and
Andrzej Lingas and
Johan Nilsson Approximation algorithms for
optimization problems in graphs with
superlogarithmic treewidth . . . . . . . 49--53
Evan J. Griffiths and
Pekka Orponen Optimization, block designs and No Free
Lunch theorems . . . . . . . . . . . . . 55--61
Ji-Bo Wang and
Zun-Quan Xia Scheduling jobs under decreasing linear
deterioration . . . . . . . . . . . . . 63--69
Angela Bonifati and
Stefano Ceri and
Stefano Paraboschi Event Trace Independence of active
behavior . . . . . . . . . . . . . . . . 71--77
Annabelle McIver and
Carroll Morgan An elementary proof that Herman's Ring
is $\Theta(N^2)$ . . . . . . . . . . . . 79--84
Roy Friedman and
Achour Mostefaoui and
Michel Raynal Asynchronous bounded lifetime failure
detectors . . . . . . . . . . . . . . . 85--91
M. Sohel Rahman and
M. Kaykobad Complexities of some interesting
problems on spanning trees . . . . . . . 93--97
Anonymous Board of Editors . . . . . . . . . . . . ??
G. Appa and
D. Magos and
I. Mourtos On the system of two all\_different
predicates . . . . . . . . . . . . . . . 99--105
Christian Liebchen and
Romeo Rizzi A greedy approach to compute a minimum
cycle basis of a directed graph . . . . 107--112
L. S. Chandran and
C. Mannino and
G. Oriolo On the cubicity of certain graphs . . . 113--118
Guang Xu and
Jinhui Xu An LP rounding algorithm for
approximating uncapacitated facility
location problem with penalties . . . . 119--123
Kuo-Chu Lee and
Chi-Hung Tzeng and
Shing-Tsaan Huang A space-efficient self-stabilizing
algorithm for measuring the size of ring
networks . . . . . . . . . . . . . . . . 125--130
J. Y. Guo and
F. K. Hwang An almost-linear time and linear space
algorithm for the longest common
subsequence problem . . . . . . . . . . 131--135
Mike Burmester and
Yvo Desmedt A secure and scalable Group Key Exchange
system . . . . . . . . . . . . . . . . . 137--143
Bruno Codenotti and
Daniel \vStefankovi\vc On the computational complexity of Nash
equilibria for (0,1) bimatrix games . . 145--150
Anonymous Board of Editors . . . . . . . . . . . . ??
Vesa Halava and
Tero Harju and
Michel Latteux Equality sets of prefix morphisms and
regular star languages . . . . . . . . . 151--154
Juha Honkala The class of HDT0L sequences is closed
with respect to rational functions . . . 155--158
Alex Brodsky An impossibility gap between width-4 and
width-5 permutation branching programs 159--164
Guy-Vincent Jourdan and
Hasan Ural and
Nejib Zaguia Minimizing the number of inputs while
applying adaptive test cases . . . . . . 165--169
Orestis A. Telelis and
Vassilis Zissimopoulos Absolute $o(\log m)$ error in
approximating random set covering: an
average case analysis . . . . . . . . . 171--177
Vadim V. Lozin Between 2- and 3-colorability . . . . . 179--182
Danilo Kor\vze and
Aleksander Vesel $L(2,1)$-labeling of strong products of
cycles . . . . . . . . . . . . . . . . . 183--190
Jun-Ming Xu and
Min Lü and
Meijie Ma and
Angelika Hellwig Super connectivity of line graphs . . . 191--195
Anonymous Board of Editors . . . . . . . . . . . . ??
Steven Minsker The Little Towers of Antwerpen problem 197--201
Ted Herman and
Colette Johnen Strategies for peer-to-peer downloading 203--209
Chuan-Min Lee and
Ling-Ju Hung and
Maw-Shang Chang and
Chia-Ben Shen and
Chuan-Yi Tang An improved algorithm for the maximum
agreement subtree problem . . . . . . . 211--216
Olivier Danvy and
Lasse R. Nielsen CPS transformation of beta-redexes . . . 217--224
Yinfeng Xu and
Wenqiang Dai and
Binhai Zhu A lower bound on the edge $l_\infty$
radius of Saitou and Nei's method for
phylogenetic reconstruction . . . . . . 225--230
Siva Anantharaman and
Paliath Narendran and
Michael Rusinowitch Closure properties and decision problems
of dag automata . . . . . . . . . . . . 231--240
Anonymous Board of Editors . . . . . . . . . . . . ??
Ph. Darondeau Equality of languages coincides with
isomorphism of reachable state graphs
for bounded and persistent Petri nets 241--245
Alexander Thomasian and
Yue Li and
Lijuan Zhang Exact $k$-NN queries on clustered SVD
datasets . . . . . . . . . . . . . . . . 247--252
Aleksander M\kadry Data exchange: On the complexity of
answering queries with inequalities . . 253--257
Sandip Das and
Partha P. Goswami and
Subhas C. Nandy Smallest $k$-point enclosing rectangle
and square of arbitrary orientation . . 259--266
J. A. Bergstra and
I. Bethke An upper bound for the equational
specification of finite state services 267--269
K. S. Cheung and
K. O. Chow Cycle inclusion property of augmented
marked graphs . . . . . . . . . . . . . 271--276
Sujatha Kashyap and
Vijay K. Garg Intractability results in predicate
detection . . . . . . . . . . . . . . . 277--282
Anonymous Subject Index --- Volume 94 (2005) . . . 283--284
Anonymous Board of Editors . . . . . . . . . . . . ??
Kimmo Fredriksson Exploiting distance coherence to speed
up range queries in metric indexes . . . 287--292
Xiaofan Yang and
David J. Evans and
Graham M. Megson Maximum induced subgraph of a recursive
circulant . . . . . . . . . . . . . . . 293--298
Ajoy K. Datta and
Maria Gradinariu and
Michel Raynal Stabilizing mobile philosophers . . . . 299--306
Shing-Tsaan Huang and
Su-Shen Hung and
Chi-Hung Tzeng Self-stabilizing coloration in anonymous
planar networks . . . . . . . . . . . . 307--312
Sebastian Deorowicz Context exhumation after the
Burrows--Wheeler transform . . . . . . . 313--320
Gopal Pandurangan On a simple randomized algorithm for
finding a 2-factor in sparse graphs . . 321--327
Piotr Faliszewski and
Janusz Jarosz Properties of uniformly hard languages 329--332
Anonymous Board of Editors . . . . . . . . . . . . ??
Zhi-Zhong Chen and
Yuusuke Okamoto and
Lusheng Wang Improved deterministic approximation
algorithms for Max TSP . . . . . . . . . 333--342
Srdjan Petrovic Space-efficient FCFS group mutual
exclusion . . . . . . . . . . . . . . . 343--350
Savio S. H. Tse A short note on the lower bound of
dilation for $O(\log n)$-label interval
routing . . . . . . . . . . . . . . . . 351--353
Gudmund Skovbjerg Frandsen and
Peter Bro Miltersen Reviewing bounds on the circuit size of
the hardest functions . . . . . . . . . 354--357
Guy Even and
Dror Rawitz and
Shimon (Moni) Shahar Hitting sets when the VC-dimension is
small . . . . . . . . . . . . . . . . . 358--362
Linh Anh Nguyen and
Rajeev Goré Completeness of hyper-resolution via the
semantics of disjunctive logic programs 363--369
Jeff Abrahamson and
Ali Shokoufandeh and
Pawel Winter Euclidean TSP between two nested convex
obstacles . . . . . . . . . . . . . . . 370--375
Anonymous Board of Editors . . . . . . . . . . . . ??
John M. Hitchcock and
A. Pavan Resource-bounded strong dimension versus
resource-bounded category . . . . . . . 377--381
Qingmin Shi and
Joseph JaJa Optimal and near-optimal algorithms for
generalized intersection reporting on
pointer machines . . . . . . . . . . . . 382--388
Bodo Manthey Non-approximability of weighted multiple
sequence alignment for arbitrary metrics 389--395
Benedek Nagy On the language equivalence of NE
star-patterns . . . . . . . . . . . . . 396--400
Jean Goubault-Larrecq Deciding $\mathcal{H}_1$ by resolution 401--408
Lu Xiao and
Howard M. Heys A simple power analysis attack against
the key schedule of the Camellia block
cipher . . . . . . . . . . . . . . . . . 409--412
Kishan Chand Gupta and
Palash Sarkar Construction of high degree resilient
S-boxes with improved nonlinearity . . . 413--417
Travis Gagie Restructuring binary search trees
revisited . . . . . . . . . . . . . . . 418--421
Anonymous Board of Editors . . . . . . . . . . . . ??
Beate Bollig A large lower bound on the query
complexity of a simple boolean function 423--428
C. Balbuena and
M. Cera and
A. Diánez and
P. García-Vázquez and
X. Marcote Sufficient conditions for
$\lambda^\prime$-optimality of graphs
with small conditional diameter . . . . 429--434
Jyh-haw Yeh and
Marion Scheepers and
Wen-chen Hu Modifying YCN key assignment scheme to
resist the attack from Hwang . . . . . . 435--440
Behrooz Parhami The Hamiltonicity of swapped (OTIS)
networks built of Hamiltonian component
networks . . . . . . . . . . . . . . . . 441--445
Salvador Lucas and
Claude Marché and
José Meseguer Operational termination of conditional
term rewriting systems . . . . . . . . . 446--453
Sophie Pinchinat and
Stéphane Riedweg A decidable class of problems for
control under partial observation . . . 454--460
Yaron Ostrovsky-Berman The transportation metric and related
problems . . . . . . . . . . . . . . . . 461--465
Justin Colannino and
Godfried Toussaint An algorithm for computing the
restriction scaffold assignment problem
in computational biology . . . . . . . . 466--471
Anonymous Board of Editors . . . . . . . . . . . . ??
Bruno Blanchet Security protocols: from linear to
classical logic by abstract
interpretation . . . . . . . . . . . . . 473--479
Kyung-Sub Min and
Hyoung-Joo Kim A path-based node filtering method for
efficient structural joins . . . . . . . 480--486
Maurice H. ter Beek and
Jetty Kleijn Modularity for teams of I/O automata . . 487--495
Ian F. Blake and
V. Kumar Murty and
Guangwu Xu A note on window $\tau$-NAF algorithm 496--502
Kengo Katayama and
Akihiro Hamamoto and
Hiroyuki Narihisa An effective local search for the
maximum clique problem . . . . . . . . . 503--511
Abraham P. Punnen and
Olena Chapovska The bottleneck $k$-MST . . . . . . . . . 512--517
Anonymous Board of Editors . . . . . . . . . . . . ??
Sander M. Bohte and
Joost N. Kok Applications of spiking neural networks 519--520
D. Verstraeten and
B. Schrauwen and
D. Stroobandt and
J. Van Campenhout Isolated word recognition with the
Liquid State Machine : a case study . . 521--528
Carl O'Dwyer and
Daniel Richardson Spiking neural nets with symbolic
internal state . . . . . . . . . . . . . 529--536
Andreas Knoblauch Neural associative memory for brain
modeling and information retrieval . . . 537--544
Nicolangelo Iannella and
Lars Kindermann Finding iterative roots with a spiking
neural network . . . . . . . . . . . . . 545--551
Olaf Booij and
Hieu tat Nguyen A gradient descent rule for spiking
neurons emitting multiple spikes . . . . 552--558
Anonymous Subject Index --- Volume 95 (2005) . . . 559--560
Anonymous Editorial Board . . . . . . . . . . . . ??
Jywe-Fei Fang and
Kuan-Chou Lai Embedding the incomplete hypercube in
books . . . . . . . . . . . . . . . . . 1--6
Dariusz Biernacki and
Olivier Danvy and
Chung-chieh Shan On the dynamic extent of delimited
continuations . . . . . . . . . . . . . 7--17
Alberto Caprara and
Ulrich Pferschy Modified subset sum heuristics for bin
packing . . . . . . . . . . . . . . . . 18--23
Andrea Pietracaprina and
Geppino Pucci Optimal many-to-one routing on the mesh
with constant queues . . . . . . . . . . 24--29
Alain Finkel and
Jérôme Leroux The convex hull of a regular set of
integer vectors is polyhedral and
effectively computable . . . . . . . . . 30--35
K. Alagarsamy A mutual exclusion algorithm with
optimally bounded bypasses . . . . . . . 36--40
Anonymous Editorial Board . . . . . . . . . . . . ??
Huaming Zhang and
Xin He Visibility representation of plane
graphs via canonical ordering tree . . . 41--48
Vassilios V. Dimakopoulos and
Leonidas Palios and
Athanasios S. Poulakidas On the Hamiltonicity of the Cartesian
product . . . . . . . . . . . . . . . . 49--53
Ferucio Lauren\ctiu \cTiplea and
Dan Cristian Marinescu Structural soundness of workflow nets is
decidable . . . . . . . . . . . . . . . 54--58
Elmar Böhler and
Steffen Reith and
Henning Schnoor and
Heribert Vollmer Bases for Boolean co-clones . . . . . . 59--66
Dieter Rautenbach Lower bounds on treespan . . . . . . . . 67--70
Rosario Gennaro and
Mario Di Raimondo Secure multiplication of shared secrets
in the exponent . . . . . . . . . . . . 71--79
Anonymous Editorial Board . . . . . . . . . . . . ??
Jérôme Monnot The labeled perfect matching in
bipartite graphs . . . . . . . . . . . . 81--88
Rocco A. Servedio and
Andrew Wan Computing sparse permanents faster . . . 89--92
Nikhil Srivastava and
Alan D. Taylor Tight bounds on plurality . . . . . . . 93--95
Sahadeo Padhye Partial known plaintext attack on Koyama
scheme . . . . . . . . . . . . . . . . . 96--100
Jianhua Zhao and
Xuandong Li and
Guoliang Zheng A quadratic-time DBM-based successor
algorithm for checking timed automata 101--105
Yuriy A. Reznik On the average depth of asymmetric
LC-tries . . . . . . . . . . . . . . . . 106--113
Swastik Kopparty and
Chinya V. Ravishankar A framework for pursuit evasion games in
$\mathbb{R}^n$ . . . . . . . . . . . . . 114--122
Anonymous Editorial Board . . . . . . . . . . . . ??
Jun-Ming Xu and
Min Xu and
Qiang Zhu The super connectivity of shuffle-cubes 123--127
Pangfeng Liu Minimum degree triangulation for
rectangular domains . . . . . . . . . . 128--135
Min Xu and
Jun-Ming Xu Edge-pancyclicity of Möbius cubes . . . . 136--140
Agostino Capponi and
Concetta Pilotto Bounded families for the on-line
$t$-relaxed coloring . . . . . . . . . . 141--145
Jun-Ming Xu and
Zheng-Zhong Du and
Min Xu Edge-fault-tolerant edge-bipancyclicity
of hypercubes . . . . . . . . . . . . . 146--150
Greg Aloupis and
Erin McLeish A lower bound for computing Oja depth 151--153
Anonymous Editorial Board . . . . . . . . . . . . ??
Tadao Takaoka An $O(n^3 \log \log n / \log n)$ time
algorithm for the all-pairs shortest
path problem . . . . . . . . . . . . . . 155--161
Walter A. Burkhard Double hashing with passbits . . . . . . 162--166
Xianbing Wang and
Yong Meng Teo and
Jiannong Cao A bivalency proof of the lower bound for
uniform consensus . . . . . . . . . . . 167--174
Igor E. Shparlinski and
Arne Winterhof On the linear complexity of bounded
integer sequences over different moduli 175--177
Gonzalo Navarro and
Nieves Brisaboa New bounds on $D$-ary optimal codes . . 178--184
Moritz G. Maaß and
Johannes Nowak A new method for approximate indexing
and dictionary lookup with one error . . 185--191
Anonymous Editorial Board . . . . . . . . . . . . ??
Ali Sezgin and
Ganesh Gopalakrishnan On the definition of sequential
consistency . . . . . . . . . . . . . . 193--196
Kuan-Yu Chen and
Kun-Mao Chao Optimal algorithms for locating the
longest and shortest segments satisfying
a sum or an average constraint . . . . . 197--201
Stasys Jukna On the P versus NP intersected with
co-NP question in communication
complexity . . . . . . . . . . . . . . . 202--206
Méziane A\"\ider and
Mustapha Aouchiche Distance monotonicity and a new
characterization of Hamming graphs . . . 207--213
Eduardo Moreno De Bruijn sequences and De Bruijn graphs
for a general language . . . . . . . . . 214--219
Bo\vstjan Slivnik and
Bo\vstjan Vilfan Producing the left parse during
bottom-up parsing . . . . . . . . . . . 220--224
Thuy Duong Vu The compression structure of a process 225--229
Anonymous Subject Index --- Volume 96 (2005) . . . 230--231
Anonymous Editorial Board . . . . . . . . . . . . ??
Feifeng Zheng and
Francis Y. L. Chin and
Stanley P. Y. Fung and
Chung Keung Poon and
Yinfeng Xu A tight lower bound for job scheduling
with cancellation . . . . . . . . . . . 1--3
Xiaotie Deng and
Li-Sha Huang On the complexity of market equilibria
with maximum social welfare . . . . . . 4--11
Amos Beimel and
Enav Weinreb Monotone circuits for monotone weighted
threshold functions . . . . . . . . . . 12--18
Oswin Aichholzer and
Franz Aurenhammer and
Clemens Huemer and
Hannes Krasser Transforming spanning trees and
pseudo-triangulations . . . . . . . . . 19--22
Haim Kaplan and
Nira Shafrir The greedy algorithm for edit distance
with moves . . . . . . . . . . . . . . . 23--27
Bolette Ammitzbòll Madsen An algorithm for Exact Satisfiability
analysed with the number of clauses as
parameter . . . . . . . . . . . . . . . 28--30
Uriel Feige and
Daniel Reichman On the hardness of approximating
Max-Satisfy . . . . . . . . . . . . . . 31--35
Salvatore Caporaso A decidable characterization of the
classes between lintime and exptime . . 36--40
Anonymous Editorial Board . . . . . . . . . . . . ??
Jacques Dubrois and
Jean-Guillaume Dumas Efficient polynomial time algorithms
computing industrial-strength primitive
roots . . . . . . . . . . . . . . . . . 41--45
René Vestergaard A constructive approach to sequential
Nash equilibria . . . . . . . . . . . . 46--51
Mitsugu Iwamoto and
Hirosuke Yamamoto Strongly secure ramp secret sharing
schemes for general access structures 52--57
Christel Baier and
Nathalie Bertrand and
Philippe Schnoebelen A note on the attractor-property of
infinite-state Markov chains . . . . . . 58--63
Wen-Hung Kuo and
Dar-Li Yang Minimizing the makespan in a single
machine scheduling problem with a
time-based learning effect . . . . . . . 64--67
Marek Chrobak and
Claire Kenyon and
Neal Young The reverse greedy algorithm for the
metric $k$-median problem . . . . . . . 68--72
Guohui Lin and
Zhipeng Cai and
Dekang Lin Vertex covering by paths on trees with
its applications in machine translation 73--81
Anonymous Editorial Board . . . . . . . . . . . . ??
Sangwon Kim and
Joonwon Lee and
Jinsoo Kim Runtime feasibility check for
non-preemptive real-time periodic tasks 83--87
Xiaofan Yang and
Jianqiu Cao and
Graham M. Megson and
Jun Luo Minimum neighborhood in a generalized
cube . . . . . . . . . . . . . . . . . . 88--93
Jun-Ming Xu and
Meijie Ma and
Min Lü Paths in Möbius cubes and crossed cubes 94--97
Bruno Escoffier and
Jérôme Monnot and
Vangelis Th. Paschos Weighted Coloring: further complexity
and approximability results . . . . . . 98--103
S. Brlek and
S. Hamadou and
J. Mullins A flaw in the electronic commerce
protocol SET . . . . . . . . . . . . . . 104--108
Jiong Guo and
Rolf Niedermeier A fixed-parameter tractability result
for multicommodity demand flow in trees 109--114
Wenjun Xiao and
Behrooz Parhami Cayley graphs as models of deterministic
small-world networks . . . . . . . . . . 115--117
Jung Hee Cheon and
Woo-Hwan Kim and
Hyun Soo Nam Known-plaintext cryptanalysis of the
Domingo--Ferrer algebraic privacy
homomorphism scheme . . . . . . . . . . 118--123
Yuan Li and
T. W. Cusick Linear structures of symmetric functions
over finite fields . . . . . . . . . . . 124--127
Anonymous Editorial Board . . . . . . . . . . . . ??
(Ben) P. C. Li and
M. Toulouse Variations of the maximum leaf spanning
tree problem for bipartite graphs . . . 129--132
Travis Gagie Compressing probability distributions 133--137
Zhenming Chen and
Evanthia Papadopoulou and
Jinhui Xu Robustness of $k$-gon Voronoi diagram
construction . . . . . . . . . . . . . . 138--145
Zheng Sun and
Tian-Ming Bu On discretization methods for
approximating optimal paths in regions
with direction-dependent costs . . . . . 146--152
Hossein Ghodosi and
Rahim Zaare-Nahandi Comments on the `$m$ out of $n$
oblivious transfer' . . . . . . . . . . 153--155
Mohammad Taghi Hajiaghayi and
Harald Räcke An $O(\sqrt{n})$-approximation algorithm
for directed sparsest cut . . . . . . . 156--160
N. Lesh and
M. Mitzenmacher BubbleSearch: A simple heuristic for
improving priority-based greedy
algorithms . . . . . . . . . . . . . . . 161--169
Anonymous Editorial Board . . . . . . . . . . . . ??
Yves F. Verhoeven Enhanced algorithms for Local Search . . 171--176
Adam Kasperski and
Pawe\l Zieli\'nski An approximation algorithm for interval
data minmax regret combinatorial
optimization problems . . . . . . . . . 177--180
Pavlos S. Efraimidis and
Paul G. Spirakis Weighted random sampling with a
reservoir . . . . . . . . . . . . . . . 181--185
Morteza Fayyazi and
David Kaeli and
Waleed Meleis An adjustable linear time parallel
algorithm for maximum weight bipartite
matching . . . . . . . . . . . . . . . . 186--190
Fedor V. Fomin and
Kjartan Hòie Pathwidth of cubic graphs and exact
algorithms . . . . . . . . . . . . . . . 191--196
Ewa Misio\lek and
Danny Z. Chen Two flow network simplification
algorithms . . . . . . . . . . . . . . . 197--202
Kang Li and
Lusheng Wang A polynomial time approximation scheme
for embedding a directed hypergraph on a
ring . . . . . . . . . . . . . . . . . . 203--207
Mark Adcock and
Richard Cleve and
Kazuo Iwama and
Raymond Putra and
Shigeru Yamashita Quantum lower bounds for the
Goldreich--Levin problem . . . . . . . . 208--211
Anonymous Editorial Board . . . . . . . . . . . . ??
Stéphanie Delaune Easy intruder deduction problems with
homomorphisms . . . . . . . . . . . . . 213--218
Bo Gyeong Kang and
Je Hong Park On the relationship between squared
pairings and plain pairings . . . . . . 219--224
Nicolas Markey and
Philippe Schnoebelen Mu-calculus path checking . . . . . . . 225--230
Mirela Damian and
Sriram V. Pemmaraju APX-hardness of domination problems in
circle graphs . . . . . . . . . . . . . 231--237
Jeng Farn Lee and
Meng Chang Chen and
Ming Tat Ko and
Wanjiun Liao Bandwidth allocation algorithms for
weighted maximum rate constrained link
sharing policy . . . . . . . . . . . . . 238--243
Dungjade Shiowattana and
Satyanarayana V. Lokam An optimal lower bound for 2-query
locally decodable linear codes . . . . . 244--250
Anonymous Subject Index --- Volume 97 (2006) . . . 251--252
Anonymous Editorial Board . . . . . . . . . . . . ??
Fanyu Kong and
Zhun Cai and
Jia Yu and
Daxing Li Improved generalized Atkin algorithm for
computing square roots in finite fields 1--5
Henrik Brosenne and
Matthias Homeister and
Stephan Waack Nondeterministic ordered binary decision
diagrams with repeated tests and various
modes of acceptance . . . . . . . . . . 6--10
C. Bernardeschi and
G. Lettieri and
L. Martini and
P. Masci Using postdomination to reduce space
requirements of data flow analysis . . . 11--18
Marc Mosko and
J. J. Garcia-Luna-Aceves Fraction interpolation walking a Farey
tree . . . . . . . . . . . . . . . . . . 19--23
Mikko Koivisto Optimal 2-constraint satisfaction via
sum--product algorithms . . . . . . . . 24--28
Minghui Jiang Approximating minimum coloring and
maximum independent set in dotted
interval graphs . . . . . . . . . . . . 29--33
Jing-Chao Chen A simple algorithm for in-place merging 34--40
Anonymous Editorial Board . . . . . . . . . . . . ??
Jigang Wu and
Thambipillai Srikanthan Low-complex dynamic programming
algorithm for hardware/software
partitioning . . . . . . . . . . . . . . 41--46
Borislav Nikolik Test suite oscillations . . . . . . . . 47--55
R. M. Hierons Applying adaptive test cases to
nondeterministic implementations . . . . 56--60
Paolo Liberatore On the complexity of extension checking
in default logic . . . . . . . . . . . . 61--65
Shiri Dori and
Gad M. Landau Construction of Aho--Corasick automaton
in linear time for integer alphabets . . 66--72
Gur Mosheiov and
Daniel Oron Single machine scheduling with
batch-dependent setup times . . . . . . 73--78
Daniel Berend and
Amir Sapir The diameter of Hanoi graphs . . . . . . 79--85
Anonymous Editorial Board . . . . . . . . . . . . ??
Claudson Bornstein and
Celina M. H. de Figueiredo and
Vinícius G. P. de Sá The Pair Completion algorithm for the
Homogeneous Set Sandwich Problem . . . . 87--91
Refael Hassin and
Shlomi Rubinstein An improved approximation algorithm for
the metric maximum clustering problem
with given cluster sizes . . . . . . . . 92--95
Dariusz Dereniowski and
Adam Nadolski Vertex rankings of chordal graphs and
weighted trees . . . . . . . . . . . . . 96--100
San Skulrattanakulchai $\Delta$-List vertex coloring in linear
time . . . . . . . . . . . . . . . . . . 101--106
Shailesh Patil and
Vijay K. Garg Adaptive general perfectly periodic
scheduling . . . . . . . . . . . . . . . 107--114
Mehri Javanian and
Mohammad Q. Vahidi-Asl Depth of nodes in random recursive
$k$-ary trees . . . . . . . . . . . . . 115--118
Li Chunlin and
Li Layuan QoS based resource scheduling by
computational economy in computational
grid . . . . . . . . . . . . . . . . . . 119--126
Anonymous Editorial Board . . . . . . . . . . . . ??
Uwe Schöning Smaller superconcentrators of density
$28$ . . . . . . . . . . . . . . . . . . 127--129
Yijie Han Improved algorithm for the symmetry
number problem on trees . . . . . . . . 130--132
Andreas Brandstädt and
Van Bang Le Structure and linear time recognition of
3-leaf powers . . . . . . . . . . . . . 133--138
Renato C. Dutra and
Valmir C. Barbosa Finding routes in anonymous sensor
networks . . . . . . . . . . . . . . . . 139--144
Joachim Kneis and
Daniel Mölle and
Stefan Richter and
Peter Rossmanith Parameterized power domination
complexity . . . . . . . . . . . . . . . 145--149
Sebastian Hack and
Gerhard Goos Optimal register allocation for SSA-form
programs in polynomial time . . . . . . 150--155
Dieter Hofbauer and
Johannes Waldmann Termination of $a a \rightarrow b c$, $b
b \rightarrow a c$, $c c \rightarrow a
b$ . . . . . . . . . . . . . . . . . . . 156--158
Rao Li A new sufficient condition for
Hamiltonicity of graphs . . . . . . . . 159--161
Eyal Ackerman and
Gill Barequet and
Ron Y. Pinter and
Dan Romik The number of guillotine partitions in
$d$ dimensions . . . . . . . . . . . . . 162--167
Anonymous Editorial Board . . . . . . . . . . . . ??
Wang Weifan and
Wang Yiqiao $L(p, q)$-labelling of $K_4$-minor free
graphs . . . . . . . . . . . . . . . . . 169--173
Andrzej Szepietowski A note on alternating one-pebble Turing
machines with sublogarithmic space . . . 174--176
J. Chen and
R. M. Hierons and
H. Ural Overcoming observability problems in
distributed test architectures . . . . . 177--182
Nikolaj Tatti Computational complexity of queries
based on itemsets . . . . . . . . . . . 183--187
Patricia Bouyer and
Thomas Brihaye and
Nicolas Markey Improved undecidability results on
weighted timed automata . . . . . . . . 188--194
Aaron Stump and
Bernd Löchner Knuth--Bendix completion of theories of
commuting group endomorphisms . . . . . 195--198
J. M. Díaz-Báñez and
M. A. López and
J. A. Sellar\`es On finding a widest empty $1$-corner
corridor . . . . . . . . . . . . . . . . 199--205
N. Raja and
R. K. Shyamasundar A closer look at constraints as
processes . . . . . . . . . . . . . . . 206--210
Anonymous Editorial Board . . . . . . . . . . . . ??
Patrick Cégielski and
Ir\`ene Guessarian and
Yuri Matiyasevich Multiple serial episodes matching . . . 211--218
Ichiro Mitsuhashi and
Michio Oyamaguchi and
Toshiyuki Yamada The reachability and related decision
problems for monadic and
semi-constructor TRSs . . . . . . . . . 219--224
Enrique Alba and
Bernabé Dorronsoro Computing nine new best-so-far solutions
for Capacitated VRP with a cellular
Genetic Algorithm . . . . . . . . . . . 225--230
Narad Rampersad The state complexity of $L^2$ and $L^k$ 231--234
Mickaël Montassier and
André Raspaud A note on 2-facial coloring of plane
graphs . . . . . . . . . . . . . . . . . 235--241
Lucian Ilie and
Solomon Marcus and
Ion Petre Periodic and Sturmian languages . . . . 242--246
Mohammad Hosseini Dolama and
Éric Sopena On the oriented chromatic number of
Halin graphs . . . . . . . . . . . . . . 247--252
Yangjun Chen and
Yibin Chen A new tree inclusion algorithm . . . . . 253--262
Anonymous Subject Index --- Volume 98 (2006) . . . 263--264
Anonymous Editorial Board . . . . . . . . . . . . ??
Huaming Zhang and
Xin He On simultaneous straight-line grid
embedding of a planar graph and its dual 1--6
Robert E. Jamison and
Gretchen L. Matthews and
John Villalpando Acyclic colorings of products of trees 7--12
Mitre C. Dourado and
Fábio Protti and
Jayme L. Szwarcfiter Complexity aspects of generalized Helly
hypergraphs . . . . . . . . . . . . . . 13--18
Yangjun Chen On the cost of searching signature trees 19--26
Christian Choffrut and
Serge Grigorieff Separability of rational relations in
$A^* \times \mathbb{N}^m$ by
recognizable relations is decidable . . 27--32
Anca Muscholl and
Mathias Samuelides and
Luc Segoufin Complementing deterministic tree-walking
automata . . . . . . . . . . . . . . . . 33--39
Anonymous Editorial Board . . . . . . . . . . . . ??
Angelika Hellwig and
Lutz Volkmann Lower bounds on the vertex-connectivity
of digraphs and graphs . . . . . . . . . 41--46
Chen Min and
Wang Weifan The 2-dipath chromatic number of Halin
graphs . . . . . . . . . . . . . . . . . 47--53
Amitabha Bagchi and
Ankur Bhargava and
Torsten Suel Approximate maximum weight branchings 54--58
Kathie Cameron and
Chính T. Ho\`ang On the structure of certain intersection
graphs . . . . . . . . . . . . . . . . . 59--63
Chung-Ming Lin and
Yin Te Tsai and
Chuan Yi Tang Balancing minimum spanning trees and
multiple-source minimum routing cost
spanning trees on metric graphs . . . . 64--67
Mickaël Montassier A note on the not 3-choosability of some
families of planar graphs . . . . . . . 68--71
Olga Xirotiri Simulation of simultaneous safe
recursion over an arbitrary structure 72--81
Anonymous Editorial Board . . . . . . . . . . . . ??
Konstantinos Bletsas and
Neil Audsley Optimal priority assignment in the
presence of blocking . . . . . . . . . . 83--86
Adi Avidor and
Ricky Rosen A note on Unique Games . . . . . . . . . 87--91
Marcin Peczarski An improvement of the tree code
construction . . . . . . . . . . . . . . 92--95
Seth Voorhies and
Hyunyoung Lee and
Andreas Klappenecker Fair service for mice in the presence of
elephants . . . . . . . . . . . . . . . 96--101
T. C. E. Cheng and
C. T. Ng and
Vladimir Kotov A new algorithm for online
uniform-machine scheduling to minimize
the makespan . . . . . . . . . . . . . . 102--105
Shih-Chien Chou and
Yuan-Chien Chen Retrieving reusable components with
variation points from software product
lines . . . . . . . . . . . . . . . . . 106--110
Sándor Vágvölgyi Descendants of a recognizable tree
language for sets of linear monadic term
rewrite rules . . . . . . . . . . . . . 111--118
Stefan Hougardy and
Doratha E. Vinkemeier Approximating weighted matchings in
parallel . . . . . . . . . . . . . . . . 119--123
Anonymous Editorial Board . . . . . . . . . . . . ??
Minghui Jiang A new approximation algorithm for
labeling points with circle pairs . . . 125--129
Raphael Yuster Finding and counting cliques and
independent sets in $r$-uniform
hypergraphs . . . . . . . . . . . . . . 130--134
Chik How Tan Analysis of improved signcryption scheme
with key privacy . . . . . . . . . . . . 135--138
Guangjun Xu and
Liying Kang and
Erfang Shan Acyclic domination on bipartite
permutation graphs . . . . . . . . . . . 139--144
Boaz Tsaban Fast generators for the Diffie--Hellman
key agreement protocol and malicious
standards . . . . . . . . . . . . . . . 145--148
Wei Huang and
Yaoyun Shi and
Shengyu Zhang and
Yufan Zhu The communication complexity of the
Hamming distance problem . . . . . . . . 149--153
Marten van Dijk and
Tom Kevenaar and
Geert-Jan Schrijen and
Pim Tuyls Improved constructions of secret sharing
schemes by applying $(\lambda,
\omega)$-decompositions . . . . . . . . 154--157
Olivier Danvy and
Henning Korsholm Rohde On obtaining the Boyer--Moore
string-matching algorithm by partial
evaluation . . . . . . . . . . . . . . . 158--162
Satoshi Ikeda and
Koji Nakazawa Strong normalization proofs by
CPS-translations . . . . . . . . . . . . 163--170
Anonymous Editorial Board . . . . . . . . . . . . ??
Yasuhiko Takenaga and
Toby Walsh Tetravex is NP-complete . . . . . . . . 171--174
Alistair Moffat and
Vo Ngoc Anh Binary codes for locally homogeneous
sequences . . . . . . . . . . . . . . . 175--180
Markus Kuba On Quickselect, partial sorting and
Multiple Quickselect . . . . . . . . . . 181--186
Asaf Levin Real time scheduling with a budget:
Parametric-search is better than binary
search . . . . . . . . . . . . . . . . . 187--191
Shisheng Li and
Guangzhong Sun and
Guoliang Chen Improved algorithm for finding
next-to-shortest paths . . . . . . . . . 192--194
Julián Mestre On the multi-radius cover problem . . . 195--198
Philippe Janssen and
Lhouari Nourine Minimum implicational basis for
$\Lambda$-semidistributive lattices . . 199--202
Yoshifumi Sakai A linear space algorithm for computing a
longest common increasing subsequence 203--207
Raymond Devillers and
Laurent Van Begin Boundedness undecidability for
synchronized nets . . . . . . . . . . . 208--214
Anonymous Editorial Board . . . . . . . . . . . . ??
André Große and
Jörg Rothe and
Gerd Wechsung On computing the smallest four-coloring
of planar graphs and non-self-reducible
sets in P . . . . . . . . . . . . . . . 215--221
Stavros Tripakis Folk theorems on the determinization and
minimization of timed automata . . . . . 222--226
C. R. Subramanian Analysis of a heuristic for acyclic edge
colouring . . . . . . . . . . . . . . . 227--229
Adrian Kosowski and
Micha\l Ma\lafiejski and
Pawe\l \.Zyli\'nski An approximation algorithm for maximum
$P_3$-packing in subcubic graphs . . . . 230--233
Amin Coja-Oghlan and
Lars Kuhtz An improved algorithm for approximating
the chromatic number of $G_{n, p}$ . . . 234--238
Felix Fischer and
Markus Holzer and
Stefan Katzenbeisser The influence of neighbourhood and
choice on the complexity of finding pure
Nash equilibria . . . . . . . . . . . . 239--245
Travis Gagie Large alphabets and incompressibility 246--251
Anonymous Subject Index --- Volume 99 (2006) . . . 252--253
Anonymous Editorial Board . . . . . . . . . . . . ??
Yunlei Zhao A note on the Dwork--Naor timed deniable
authentication . . . . . . . . . . . . . 1--7
Ioannis Koutis Parameterized complexity and improved
inapproximability for computing the
largest $j$-simplex in a $V$-polytope 8--13
Sebastian Deorowicz Speeding up transposition-invariant
string matching . . . . . . . . . . . . 14--20
Dongvu Tonien On a traitor tracing scheme from ACISP
2003 . . . . . . . . . . . . . . . . . . 21--22
Arvind Narayanan and
K. Srinathan and
C. Pandu Rangan Perfectly Reliable Message Transmission 23--28
Eric Angel and
Evripidis Bampis and
Lélia Blin and
Laurent Gourv\`es Fair cost-sharing methods for the
minimum spanning tree game . . . . . . . 29--35
Ted Krovetz and
Phillip Rogaway Variationally universal hashing . . . . 36--39
Anonymous Editorial Board . . . . . . . . . . . . ??
Guy Wolfovitz The complexity of depth-$3$ circuits
computing symmetric Boolean functions 41--46
Iztok Bani\vc and
Janez \vZerovnik Fault-diameter of Cartesian graph
bundles . . . . . . . . . . . . . . . . 47--51
Yosuke Kikuchi and
Toru Araki Edge-bipancyclicity and
edge-fault-tolerant bipancyclicity of
bubble-sort graphs . . . . . . . . . . . 52--59
Ernesto Jiménez and
Sergio Arévalo and
Antonio Fernández Implementing unreliable failure
detectors with unknown membership . . . 60--63
Peter Damaschke A remark on the subsequence problem for
arc-annotated sequences with pairwise
nested arcs . . . . . . . . . . . . . . 64--68
Khaled Elbassioni and
Zvi Lotker and
Raimund Seidel Upper bound on the number of vertices of
polyhedra with $0, 1$-constraint
matrices . . . . . . . . . . . . . . . . 69--71
Martin Lange and
Rafa\l Somla Propositional dynamic logic of
context-free programs and fixpoint logic
with chop . . . . . . . . . . . . . . . 72--75
Pum-Mo Ryu and
Key-Sun Choi Determining the specificity of terms
using inside--outside information: a
necessary condition of term hierarchy
mining . . . . . . . . . . . . . . . . . 76--82
Jyh-Shyan Lin and
Jen-Chun Chang and
Rong-Jaye Chen New simple constructions of
distance-increasing mappings from binary
vectors to permutations . . . . . . . . 83--89
Anonymous Editorial Board . . . . . . . . . . . . ??
Kimmo Fredriksson and
Maxim Mozgovoy Efficient parameterized string matching 91--96
Alexandre Pinlou and
Éric Sopena Oriented vertex and arc colorings of
outerplanar graphs . . . . . . . . . . . 97--104
Tatsuya Akutsu A relation between edit distance for
ordered trees and edit distance for
Euler strings . . . . . . . . . . . . . 105--109
Xianchao Zhang and
Weifa Liang and
He Jiang Flow equivalent trees in undirected
node-edge-capacitated planar graphs . . 110--115
André Gronemeier A note on the decoding complexity of
error-correcting codes . . . . . . . . . 116--119
Asish Mukhopadhyay and
Samidh Chatterjee and
Benjamin Lafreniere On the All-Farthest-Segments problem for
a planar set of points . . . . . . . . . 120--123
Artiom Alhazov P systems without multiplicities of
symbol-objects . . . . . . . . . . . . . 124--129
Anonymous Editorial Board . . . . . . . . . . . . ??
Jean-Luc Baril and
Jean-Marcel Pallo Efficient lower and upper bounds of the
diagonal-flip distance between
triangulations . . . . . . . . . . . . . 131--136
Z. S. Peng and
H. F. Ting An $O(n \log n)$-time algorithm for the
maximum constrained agreement subtree
problem for binary trees . . . . . . . . 137--144
Andrew Teoh and
Beng Jin and
Tee Connie and
David Ngo and
Chek Ling Remarks on BioHash and its mathematical
foundation . . . . . . . . . . . . . . . 145--150
Yunfeng Tao Infinity problems and countability
problems for $\omega$-automata . . . . . 151--153
Chor Ping Low An approximation algorithm for the
load-balanced semi-matching problem in
weighted bipartite graphs . . . . . . . 154--161
Reuven Cohen and
Liran Katzir and
Danny Raz An efficient approximation for the
Generalized Assignment Problem . . . . . 162--166
Gang Wu and
Jia-Huai You and
Guohui Lin A polynomial time algorithm for the
minimum quartet inconsistency problem
with $O(n)$ quartet errors . . . . . . . 167--171
Anonymous Editorial Board . . . . . . . . . . . . ??
Enrique Alba and
Gabriel Luque and
Lourdes Araujo Natural language tagging with genetic
algorithms . . . . . . . . . . . . . . . 173--182
Xuehou Tan A $2$-approximation algorithm for the
Zookeeper's Problem . . . . . . . . . . 183--187
Calin D. Morosan On the number of broadcast schemes in
networks . . . . . . . . . . . . . . . . 188--193
Jianbo Qian and
Cao An Wang How much precision is needed to compare
two sums of square roots of integers? 194--198
Taisuke Izumi and
Toshimitsu Masuzawa A weakly-adaptive condition-based
consensus algorithm in asynchronous
distributed systems . . . . . . . . . . 199--205
Joost Engelfriet and
Sebastian Maneth The equivalence problem for
deterministic MSO tree transducers is
decidable . . . . . . . . . . . . . . . 206--212
Anonymous Editorial Board . . . . . . . . . . . . ??
Akiyoshi Shioura and
Takeshi Tokuyama Efficiently pricing European-Asian
options-ultimate implementation and
analysis of the AMO algorithm . . . . . 213--219
F. Aurenhammer and
R. L. S. Drysdale and
H. Krasser Farthest line segment Voronoi diagrams 220--225
Kimmo Fredriksson and
Szymon Grabowski A general compression algorithm that
supports fast searching . . . . . . . . 226--232
Hong Liu and
Kenneth W. Regan Improved construction for universality
of determinant and permanent . . . . . . 233--237
Alon Efrat and
Sariel Har-Peled Guarding galleries and terrains . . . . 238--245
Anonymous Author Index --- Volume 100 (2006) . . . 246--247
Joost Engelfriet and
Tjalling Gelsema An exercise in structural congruence . . 1--5
Houman Alborzi and
Hanan Samet Execution time analysis of a top-down
R-tree construction algorithm . . . . . 6--12
Eric Mc Dermid and
Christine Cheng and
Ichiro Suzuki Hardness results on the man-exchange
stable marriage problem with short
preference lists . . . . . . . . . . . . 13--19
Junhu Wang Binary equality implication constraints,
normal forms and data redundancy . . . . 20--25
Uriel Feige and
James R. Lee An improved approximation ratio for the
minimum linear arrangement problem . . . 26--29
Vardges Melkonian Flows in dynamic networks with aggregate
arc capacities . . . . . . . . . . . . . 30--35
Faisal N. Abu-Khzam and
Michael A. Langston Linear-time algorithms for problems on
planar graphs with fixed disk dimension 36--40
Richard S. Bird and
Stefan Sadnicki Minimal on-line labelling . . . . . . . 41--45
Yoshinobu Kawabe and
Ken Mano and
Hideki Sakurada and
Yasuyuki Tsukada Theorem-proving anonymity of
infinite-state systems . . . . . . . . . 46--51
Anonymous Editorial Board . . . . . . . . . . . . ??
Peter Clifford and
Raphaël Clifford Simple deterministic wildcard matching 53--54
M. H. Albert and
M. D. Atkinson and
Doron Nussbaum and
Jörg-Rüdiger Sack and
Nicola Santoro On the longest increasing subsequence of
a circular list . . . . . . . . . . . . 55--59
Ittai Abraham and
Gregory Chockler and
Idit Keidar and
Dahlia Malkhi Wait-free regular storage from Byzantine
components . . . . . . . . . . . . . . . 60--65
Daniel Sawitzki Lower bounds on the OBDD size of two
fundamental functions' graphs . . . . . 66--71
Yuuki Tanaka and
Hiroyuki Kawai and
Yukio Shibata Isomorphic factorization, the Kronecker
product and the line digraph . . . . . . 72--77
Moon Bae Song and
Kwang Jin Park and
Ki-Sik Kong and
Sang Keun Lee Bottom-up nearest neighbor search for
R-trees . . . . . . . . . . . . . . . . 78--85
Eric Bach Bounds for the expected duration of the
monopolist game . . . . . . . . . . . . 86--92
Anonymous Editorial Board . . . . . . . . . . . . ??
Chang-Hsiung Tsai and
Shu-Yun Jiang Path bipancyclicity of hypercubes . . . 93--97
Lev Reyzin and
Nikhil Srivastava On the longest path algorithm for
reconstructing trees from distance
matrices . . . . . . . . . . . . . . . . 98--100
Tobias Riege and
Jörg Rothe and
Holger Spakowski and
Masaki Yamamoto An improved exact algorithm for the
domatic number problem . . . . . . . . . 101--106
Ulrich Ultes-Nitsche A power-set construction for reducing
Büchi automata to non-determinism degree
two . . . . . . . . . . . . . . . . . . 107--111
Dana Ron and
Amir Rosenfeld and
Salil Vadhan The hardness of the Expected Decision
Depth problem . . . . . . . . . . . . . 112--118
Maria Patricia Dobson and
Marisa Gutierrez and
Michel Habib and
Jayme L. Szwarcfiter On transitive orientations with
restricted covering graphs . . . . . . . 119--125
Marcin Peczarski The Ford--Johnson algorithm still
unbeaten for less than $47$ elements . . 126--128
Michael J. Collins and
David Kempe and
Jared Saia and
Maxwell Young Nonnegative integral subset
representations of integer sets . . . . 129--133
Min Chen and
André Raspaud and
Weifan Wang Three-coloring planar graphs without
short cycles . . . . . . . . . . . . . . 134--138
Anonymous Editorial Board . . . . . . . . . . . . ??
Joost Engelfriet A Kleene characterization of
computability . . . . . . . . . . . . . 139--140
Katrin Erk and
Joachim Niehren Dominance constraints in stratified
context unification . . . . . . . . . . 141--147
Leonid Khachiyan and
Endre Boros and
Khaled Elbassioni and
Vladimir Gurvich A global parallel algorithm for the
hypergraph transversal problem . . . . . 148--155
Yoann Dieudonné and
Franck Petit Circle formation of weak robots and
Lyndon words . . . . . . . . . . . . . . 156--162
Jan Krají\vcek Substitutions into propositional
tautologies . . . . . . . . . . . . . . 163--167
Chi-Hung Tzeng and
Jehn-Ruey Jiang and
Shing-Tsaan Huang A self-stabilizing $(\Delta +
4)$-edge-coloring algorithm for planar
graphs in anonymous uniform systems . . 168--173
Wenbin Chen and
Jiangtao Meng An improved lower bound for
approximating Shortest Integer Relation
in $\ell_\infty$ norm
$(\mathrm{SIR}_\infty)$ . . . . . . . . 174--179
Anonymous Editorial Board . . . . . . . . . . . . ??
David Eisenstat and
Dana Angluin The VC dimension of $k$-fold union . . . 181--184
Min Xu and
Jun-Ming Xu The forwarding indices of augmented
cubes . . . . . . . . . . . . . . . . . 185--189
Emmanuelle Anceaume and
Roy Friedman and
Maria Gradinariu Managed Agreement: Generalizing two
fundamental distributed agreement
problems . . . . . . . . . . . . . . . . 190--198
Péter Biró and
Katarína Cechlárová Inapproximability of the kidney exchange
problem . . . . . . . . . . . . . . . . 199--202
Shiyan Hu A linear time algorithm for max-min
length triangulation of a convex polygon 203--208
Carlos Martín-Vide and
Victor Mitrana Remarks on arbitrary multiple pattern
interpretations . . . . . . . . . . . . 209--214
Louis Esperet and
Pascal Ochem Oriented colorings of $2$-outerplanar
graphs . . . . . . . . . . . . . . . . . 215--219
J. Guadalupe Ramos and
Josep Silva and
Germán Vidal Ensuring the quasi-termination of needed
narrowing computations . . . . . . . . . 220--226
Anonymous Editorial Board . . . . . . . . . . . . ??
Hong-Chun Hsu and
Pao-Lien Lai and
Chang-Hsiung Tsai Geodesic pancyclicity and balanced
pancyclicity of Augmented cubes . . . . 227--232
Vardges Melkonian LP-based solution methods for the
asymmetric TSP . . . . . . . . . . . . . 233--238
Shuang Luan and
Jared Saia and
Maxwell Young Approximation algorithms for minimizing
segments in radiation therapy . . . . . 239--244
Martin Dietzfelbinger and
Henning Wunderlich A characterization of average case
communication complexity . . . . . . . . 245--249
Moritz G. Maaß Computing suffix links for suffix trees
and arrays . . . . . . . . . . . . . . . 250--254
Paulo Sérgio Almeida and
Carlos Baquero and
Nuno Preguiça and
David Hutchison Scalable Bloom Filters . . . . . . . . . 255--261
Rami Al Na'mneh and
W. David Pan Five-step FFT algorithm with reduced
computational complexity . . . . . . . . 262--267
Anonymous Editorial Board . . . . . . . . . . . . ??
Ken S. Hu and
Shyun-Shyun Yeoh and
Chiuyuan Chen and
Lih-Hsing Hsu Node-pancyclicity and edge-pancyclicity
of hypercube variants . . . . . . . . . 1--7
M. Jiang and
Y. P. Luo and
S. Y. Yang Stochastic convergence analysis and
parameter selection of the standard
particle swarm optimization algorithm 8--16
Henrik Brosenne and
Carsten Damm and
Matthias Homeister and
Stephan Waack On approximation by $\oplus$-OBDDs . . . 17--21
Wen-Hung Kuo and
Dar-Li Yang Single machine scheduling with
past-sequence-dependent setup times and
learning effects . . . . . . . . . . . . 22--26
Yung H. Tsin An improved self-stabilizing algorithm
for biconnectivity and
bridge-connectivity . . . . . . . . . . 27--34
Cho-Chin Lin and
Hao-Yun Yin Bounds on the multi-clients incremental
computing for homogeneous decreasing
computation sequences . . . . . . . . . 35--40
Anonymous Editorial Board . . . . . . . . . . . . ??
Min Ji and
T. C. E. Cheng An FPTAS for scheduling jobs with
piecewise linear decreasing processing
times to minimize makespan . . . . . . . 41--47
Zhilin Wu A note on the characterization of
$\mathrm{TL}[\mathrm{EF}]$ . . . . . . . 48--54
Joseph Wun-Tat Chan and
Francis Y. L. Chin and
Deshi Ye and
Yong Zhang and
Hong Zhu Greedy online frequency allocation in
cellular networks . . . . . . . . . . . 55--61
Jiong Guo and
Falk Hüffner and
Hannes Moser Feedback arc set in bipartite
tournaments is NP-complete . . . . . . . 62--65
Xuehou Tan Sweeping simple polygons with the
minimum number of chain guards . . . . . 66--71
Benjamin Van Roy MIN . . . . . . . . . . . . . . . . . . 72--73
Narad Rampersad On the context-freeness of the set of
words containing overlaps . . . . . . . 74--78
Hiroshi Nagamochi and
Yoko Kamidoi Minimum cost subpartitions in graphs . . 79--84
Luo Xiaofang The $4$-choosability of toroidal graphs
without intersecting triangles . . . . . 85--91
Iiro Honkala and
Tero Laihonen On a new class of identifying codes in
graphs . . . . . . . . . . . . . . . . . 92--98
Kuo-Si Huang and
Chang-Biau Yang and
Kuo-Tsung Tseng and
Yung-Hsing Peng and
Hsing-Yen Ann Dynamic programming algorithms for the
mosaic longest common subsequence
problem . . . . . . . . . . . . . . . . 99--103
Alexander A. Sherstov Powering requires threshold depth $3$ 104--107
Lenin Mehedy and
M. Kamrul Hasan and
Mohammad Kaykobad An improved degree based condition for
Hamiltonian cycles . . . . . . . . . . . 108--112
Travis Gagie Dynamic Shannon coding . . . . . . . . . 113--117
Kwangkeun Yi and
Hosik Choi and
Jaehwang Kim and
Yongdai Kim An empirical study on classification
methods for alarms from a bug-finding
static C analyzer . . . . . . . . . . . 118--123
Vaston Costa and
Edward Haeusler and
Eduardo S. Laber and
Loana Nogueira A note on the size of minimal covers . . 124--126
Fabien Laguillaumie and
Damien Vergnaud Multi-designated verifiers signatures:
anonymity without encryption . . . . . . 127--132
Anonymous Editorial Board . . . . . . . . . . . . ??
Jaume Martí-Farré A note on secret sharing schemes with
three homogeneous access structure . . . 133--137
Gildas Avoine and
Serge Vaudenay How to safely close a discussion . . . . 138--142
Min-Sheng Lin Fast and simple algorithms to count the
number of vertex covers in an interval
graph . . . . . . . . . . . . . . . . . 143--146
El\.zbieta Sidorowicz The game chromatic number and the game
colouring number of cactuses . . . . . . 147--151
Peter Brass Multidimensional heaps and complementary
range searching . . . . . . . . . . . . 152--155
Narsingh Deo and
Aurel Cami Preferential deletion in dynamic models
of web-like networks . . . . . . . . . . 156--162
Partha P. Goswami and
Sandip Das and
Subhas C. Nandy Chromatic distribution of $k$-nearest
neighbors of a line segment in a planar
colored point set . . . . . . . . . . . 163--168
Jan Vahrenhold An in-place algorithm for Klee's measure
problem in two dimensions . . . . . . . 169--174
Anonymous Editorial Board . . . . . . . . . . . . ??
Fabrizio Luccio and
Antonio Mesa Enriquez and
Linda Pagli $k$-Restricted rotation distance between
binary trees . . . . . . . . . . . . . . 175--180
Wim H. Hesselink A linear-time algorithm for Euclidean
feature transform sets . . . . . . . . . 181--186
Edward Chlebus and
Jordy Brazier Nonstationary Poisson modeling of Web
browsing session arrivals . . . . . . . 187--190
\Lukasz Kowalik Adjacency queries in dynamic sparse
graphs . . . . . . . . . . . . . . . . . 191--195
Shahram Latifi A study of fault tolerance in star graph 196--200
Mauricio Ayala-Rincón and
Bruno T. de Abreu and
José de Siqueira A variant of the Ford--Johnson algorithm
that is more space efficient . . . . . . 201--207
Laurent Doyen Robust parametric reachability for timed
automata . . . . . . . . . . . . . . . . 208--213
Richard Hammack Minimum cycle bases of direct products
of complete graphs . . . . . . . . . . . 214--218
Anonymous Editorial Board . . . . . . . . . . . . ??
Oren Ben-Zwi and
Oded Lachish and
Ilan Newman Lower bounds for testing Euclidean
Minimum Spanning Trees . . . . . . . . . 219--225
Jun-Ming Xu and
Chao Yang Fault diameter of product graphs . . . . 226--228
Thierry Lecroq Fast exact string matching algorithms 229--235
François Laroussinie and
Jeremy Sproston State explosion in almost-sure
probabilistic reachability . . . . . . . 236--241
Chang-Hsiung Tsai Cycles embedding in hypercubes with node
failures . . . . . . . . . . . . . . . . 242--246
Sidi Mohamed Sedjelmaci Jebelean--Weber's algorithm without
spurious factors . . . . . . . . . . . . 247--252
Nenad Obradovi\'c and
Joseph Peters and
Goran Ru\vzi\'c Efficient domination in circulant graphs
with two chord lengths . . . . . . . . . 253--258
Deshi Ye and
Guochuan Zhang Maximizing the throughput of parallel
jobs on hypercubes . . . . . . . . . . . 259--263
Anonymous Editorial Board . . . . . . . . . . . . ??
Robert W. Irving The cycle roommates problem: a hard case
of kidney exchange . . . . . . . . . . . 1--4
Marc Aiguier and
R\uazvan Diaconescu Stratified institutions and elementary
homomorphisms . . . . . . . . . . . . . 5--13
Hai-Lung Cheng and
Biing-Feng Wang On Chen and Chen's new tree inclusion
algorithm . . . . . . . . . . . . . . . 14--18
Seok Woo Kim and
Seong-Hun Paeng and
Hee Je Cho Approximately $n$-secting an angle . . . 19--23
Hasan Akìn and
Irfan Siap On cellular automata over Galois rings 24--27
Jukka Suomela Approximability of identifying codes and
locating--dominating codes . . . . . . . 28--33
Nikolai K. Vereshchagin Kolmogorov complexity of enumerating
finite sets . . . . . . . . . . . . . . 34--39
Min Chih Lin and
Jayme L. Szwarcfiter Faster recognition of clique-Helly and
hereditary clique-Helly graphs . . . . . 40--43
Justin Colannino and
Godfried Toussaint Corrigendum to ``An algorithm for
computing the restriction Scaffold
assignment problem in computational
biology'' [Inform. Process. Lett. 95 (4)
(2005) 466--471] . . . . . . . . . . . . 44--44
Anonymous Editorial Board . . . . . . . . . . . . ??
Brendan Lucier and
Tao Jiang and
Ming Li Average-case analysis of QuickSort and
Binary Insertion Tree height using
incompressibility . . . . . . . . . . . 45--51
Wei-Wei Wang and
Mei-Jie Ma and
Jun-Ming Xu Fault-tolerant pancyclicity of augmented
cubes . . . . . . . . . . . . . . . . . 52--56
Kofi A. Laing Name-independent compact routing in
trees . . . . . . . . . . . . . . . . . 57--60
Anonymous Editorial Board . . . . . . . . . . . . ??
Igor E. Shparlinski Bounds on the Fourier coefficients of
the weighted sum function . . . . . . . 83--87
Volker Turau Linear self-stabilizing algorithms for
the independent and dominating set
problems using an unfair distributed
scheduler . . . . . . . . . . . . . . . 88--93
Anuj Dawar and
David Janin The monadic theory of finite
representations of infinite words . . . 94--101
A. Pavan and
Fengming Wang Robustness of PSPACE-complete sets . . . 102--104
Christoph Minnameier Local and global deadlock-detection in
component-based systems are NP-hard . . 105--111
Florin Manea and
Victor Mitrana All NP-problems can be solved in
polynomial time by accepting hybrid
networks of evolutionary processors of
constant size . . . . . . . . . . . . . 112--118
Joseph Y.-T. Leung and
Haibing Li and
Michael Pinedo and
Jiawei Zhang Minimizing total weighted completion
time when scheduling orders in a
flexible environment with uniform
machines . . . . . . . . . . . . . . . . 119--129
Anonymous Editorial Board . . . . . . . . . . . . ??
Philip M. Long and
Rocco A. Servedio and
Hans Ulrich Simon Discriminative learning can succeed
where generative learning fails . . . . 131--135
Georg Gottlob and
Stephanie Tien Lee A logical approach to multicut problems 136--141
Amihood Amir and
Leszek Gasieniec and
Riva Shalom Improved approximate common interval . . 142--149
Xiaofang Luo and
Min Chen and
Weifan Wang On $3$-colorable planar graphs without
cycles of four lengths . . . . . . . . . 150--156
D. Ruiz and
R. Corchuelo and
J. L. Arjona Generating non-conspiratorial executions 157--162
Matthias Hagen On the fixed-parameter tractability of
the equivalence test of monotone normal
forms . . . . . . . . . . . . . . . . . 163--167
Anonymous Editorial Board . . . . . . . . . . . . ??
X. H. Shi and
Y. C. Liang and
H. P. Lee and
C. Lu and
Q. X. Wang Particle swarm optimization-based
algorithms for TSP and generalized TSP 169--176
Louise Leenen and
Thomas Meyer and
Aditya Ghose Relaxations of semiring constraint
satisfaction problems . . . . . . . . . 177--182
Adam Janiak and
Rados\law Rudek The learning effect: Getting to the core
of the problem . . . . . . . . . . . . . 183--187
Flemming Nielson and
Hanne Riis Nielson and
Henrik Pilegaard What is a free name in a process
algebra? . . . . . . . . . . . . . . . . 188--194
Paulo Feofiloff and
Cristina G. Fernandes and
Carlos E. Ferreira and
José Coelho de Pina Primal-dual approximation algorithms for
the Prize-Collecting Steiner Tree
Problem . . . . . . . . . . . . . . . . 195--202
Barbara König and
Vitali Kozioura Incremental construction of coverability
graphs . . . . . . . . . . . . . . . . . 203--209
Anonymous Editorial Board . . . . . . . . . . . . ??
Igor E. Shparlinski and
Arne Winterhof Quantum period reconstruction of
approximate sequences . . . . . . . . . 211--215
Shin-ichi Nakayama and
Shigeru Masuyama A polynomial time algorithm for
obtaining minimum edge ranking on
two-connected outerplanar graphs . . . . 216--221
Jun-Ming Xu and
Qiang Zhu and
Min Xu Fault-tolerant analysis of a class of
networks . . . . . . . . . . . . . . . . 222--226
Petri Kontkanen and
Petri Myllymäki A linear-time algorithm for computing
the multinomial stochastic complexity 227--233
Lutz Volkmann Restricted arc-connectivity of digraphs 234--239
Yun-Sheng Chung and
Chin Lung Lu and
Chuan Yi Tang Efficient algorithms for regular
expression constrained sequence
alignment . . . . . . . . . . . . . . . 240--246
Areej Zuhily and
Alan Burns Optimal $(D - J)$-monotonic priority
assignment . . . . . . . . . . . . . . . 247--250
Anonymous Editorial Board . . . . . . . . . . . . ??
Florian Horn Dicing on the Streett . . . . . . . . . 1--9
N. S. Narayanaswamy and
N. Belkale and
L. S. Chandran and
N. Sivadasan A note on the Hadwiger number of
circular arc graphs . . . . . . . . . . 10--13
Géraldine Jean and
Macha Nikolski Genome rearrangements: a correct
algorithm for optimal capping . . . . . 14--20
Asaf Levin The finite horizon investor problem with
a budget constraint . . . . . . . . . . 21--28
Tomá\vs Masopust and
Alexander Meduna Descriptional complexity of
semi-conditional grammars . . . . . . . 29--31
Saulius Minkevi\vcius The impact of overload conditions on
computer network reliability . . . . . . 32--35
Vlady Ravelomanana Another proof of Wright's inequalities 36--39
Anonymous Editorial Board . . . . . . . . . . . . ??
Toru Hasunuma and
Misa Hirota An improved upper bound on the
queuenumber of the hypercube . . . . . . 41--44
Guohua Wan and
Joseph Y.-T. Leung and
Michael L. Pinedo Scheduling imprecise computation tasks
on uniform processors . . . . . . . . . 45--52
Igor Razgon A $2^{O(k)} \mathrm{poly}(n)$ algorithm
for the parameterized Convex Recoloring
problem . . . . . . . . . . . . . . . . 53--58
Selim G. Akl and
Md. Kamrul Islam and
Henk Meijer On planar path transformation . . . . . 59--64
Venkatesh Raman and
Saket Saurabh Improved fixed parameter tractable
algorithms for two ``edge'' problems:
MAXCUT and MAXDAG . . . . . . . . . . . 65--72
ChenGuang Liu and
Kazuyuki Tanaka Eigen-distribution on random assignments
for game trees . . . . . . . . . . . . . 73--77
Anonymous Editorial Board . . . . . . . . . . . . ??
Venkatesh Raman and
Somnath Sikdar Parameterized complexity of the induced
subgraph problem in directed graphs . . 79--85
Toru Araki On the $k$-tuple domination of de Bruijn
and Kautz digraphs . . . . . . . . . . . 86--90
Miko\laj Boja\'nczyk A new algorithm for testing if a regular
language is locally threshold testable 91--94
Markus E. Nebel On the lexicographical generation of
compressed codes . . . . . . . . . . . . 95--100
Sylvain Duquesne Improving the arithmetic of elliptic
curves in the Jacobi model . . . . . . . 101--105
Mariano Zelke Optimal per-edge processing times in the
semi-streaming model . . . . . . . . . . 106--112
Mohammad Ghodsi and
Hamid Mahini and
Kian Mirjalali and
Shayan Oveis Gharan and
Amin S. Sayedi R. and
Morteza Zadimoghaddam Spanning trees with minimum weighted
degrees . . . . . . . . . . . . . . . . 113--116
Anonymous Editorial Board . . . . . . . . . . . . ??
Yuren Zhou and
Jun He Convergence analysis of a self-adaptive
multi-objective evolutionary algorithm
based on grids . . . . . . . . . . . . . 117--122
Wolfgang Bein and
Lawrence L. Larmore and
John Noga Uniform metrical task systems with a
limited number of states . . . . . . . . 123--128
Thomas Chatain and
Victor Khomenko On the well-foundedness of adequate
orders used for construction of complete
unfolding prefixes . . . . . . . . . . . 129--136
Piotr Berman and
Bhaskar DasGupta and
Ming-Yang Kao and
Jie Wang On constructing an optimal consensus
clustering from multiple clusterings . . 137--145
Liang Shen and
Yingqian Wang A sufficient condition for a planar
graph to be $3$-choosable . . . . . . . 146--151
Mingsheng Ying and
Jianxin Chen and
Yuan Feng and
Runyao Duan Commutativity of quantum weakest
preconditions . . . . . . . . . . . . . 152--158
Anonymous Editorial Board . . . . . . . . . . . . ??
K. Hvam and
L. Reinhardt and
P. Winter and
M. Zachariasen Bounding component sizes of
two-connected Steiner networks . . . . . 159--163
Petr Jan\vcar and
Zden\vek Sawa A note on emptiness for alternating
finite automata with a one-letter
alphabet . . . . . . . . . . . . . . . . 164--167
Rahul Roy and
Amitava Bagchi On estimating the time taken to rectify
faults in a software package during the
system testing phase . . . . . . . . . . 168--172
Hiroshi Nagamochi and
Kohei Okada Approximating the minmax rooted-tree
cover in a tree . . . . . . . . . . . . 173--178
Hossein Ghodosi On insecurity of Naor--Pinkas'
distributed oblivious transfer . . . . . 179--182
Jaechul Sung and
Deukjo Hong and
Seokhie Hong Cryptanalysis of an involutional block
cipher using cellular automata . . . . . 183--185
Michael Elkin and
Christian Liebchen and
Romeo Rizzi New length bounds for cycle bases . . . 186--193
Anonymous Editorial Board . . . . . . . . . . . . ??
E. Bertsch and
M.-J. Nederhof Some observations on LR-like parsing
with delayed reduction . . . . . . . . . 195--199
Alon Itai and
Irit Katriel Canonical density control . . . . . . . 200--204
Ilan Gronau and
Shlomo Moran Optimal implementations of UPGMA and
other common clustering algorithms . . . 205--210
Xie-Bin Chen Cycles passing through prescribed edges
in a hypercube with some faulty edges 211--215
Klaus Meer Simulated Annealing versus Metropolis
for a TSP instance . . . . . . . . . . . 216--219
Andrzej Lingas and
Agnieszka Wasylewicz and
Pawe\l \.Zyli\'nski Note on covering monotone orthogonal
polygons with star-shaped polygons . . . 220--227
Jessica Enright and
Lorna Stewart Subtree filament graphs are subtree
overlap graphs . . . . . . . . . . . . . 228--232
Anonymous Editorial Board . . . . . . . . . . . . ??
Konstantin Kutzkov New upper bound for the #3-SAT problem 1--5
Erfang Shan and
T. C. E. Cheng and
Liying Kang Absorbant of generalized de Bruijn
digraphs . . . . . . . . . . . . . . . . 6--11
J. J. Liu and
G. S. Huang and
Y. L. Wang and
R. C. T. Lee Edit distance for a run-length-encoded
string and an uncompressed string . . . 12--16
Pratik Worah and
Sandeep Sen A linear time deterministic algorithm to
find a small subset that approximates
the centroid . . . . . . . . . . . . . . 17--19
Lun-Min Shih and
Jimmy J. M. Tan and
Lih-Hsing Hsu Edge-bipancyclicity of conditional
faulty hypercubes . . . . . . . . . . . 20--25
Tetsuo Asano Aspect-ratio Voronoi diagram and its
complexity bounds . . . . . . . . . . . 26--31
Holger Petersen String matching with simple devices . . 32--34
Dawei Hong Analysis of noise-induced phase
synchronization in nervous systems: from
algorithmic perspective . . . . . . . . 35--39
Anonymous Editorial Board . . . . . . . . . . . . ??
Tian-Ming Bu and
Xiaotie Deng and
Qi Qi Forward looking Nash equilibrium for
keyword auction . . . . . . . . . . . . 41--46
R. L. Scot Drysdale and
Asish Mukhopadhyay An $O(n \log n)$ algorithm for the
all-farthest-segments problem for a
planar set of points . . . . . . . . . . 47--51
Yuri Breitbart and
Hassan Gobjuka Characterization of layer-$2$ unique
topologies . . . . . . . . . . . . . . . 52--57
Asish Mukhopadhyay and
Chanchal Kumar and
Eugene Greene and
Binay Bhattacharya On intersecting a set of parallel line
segments with a convex polygon of
minimum area . . . . . . . . . . . . . . 58--64
Guillaume Fertin and
André Raspaud Acyclic coloring of graphs of maximum
degree five: Nine colors are enough . . 65--72
Sergio Cabello and
Panos Giannopoulos and
Christian Knauer On the parameterized complexity of
$d$-dimensional point set pattern
matching . . . . . . . . . . . . . . . . 73--77
Anonymous Editorial Board . . . . . . . . . . . . ??
Prashant Sasatte Improved FPT algorithm for feedback
vertex set problem in bipartite
tournament . . . . . . . . . . . . . . . 79--82
Peyman Afshani and
Hamed Hatami Approximation and inapproximability
results for maximum clique of disc
graphs in high dimensions . . . . . . . 83--87
Nattapat Attiratanasunthron and
Jittat Fakcharoenphol A running time analysis of an Ant Colony
Optimization algorithm for shortest
paths in directed acyclic graphs . . . . 88--92
Frank Nielsen and
Richard Nock On the smallest enclosing information
disk . . . . . . . . . . . . . . . . . . 93--97
G. Araujo and
J. Balogh and
R. Fabila and
G. Salazar and
J. Urrutia A note on harmonic subgraphs in labelled
geometric graphs . . . . . . . . . . . . 98--102
Hamid Zarrabi-Zadeh Flying over a polyhedral terrain . . . . 103--107
Farshad Rostamabadi and
Iman Sadeghi and
Mohammad Ghodsi and
Ramtin Khosravi Optimal point removal in closed-2PM
labeling . . . . . . . . . . . . . . . . 108--113
Yijie Han A note of an $O(n^3 / \log n)$ time
algorithm for all pairs shortest paths 114--116
Anonymous Editorial Board . . . . . . . . . . . . ??
Jyh-haw Yeh A secure time-bound hierarchical key
assignment scheme based on RSA public
key cryptosystem . . . . . . . . . . . . 117--120
Jana Dietel and
Hans-Dietrich Hecker and
Andreas Spillner A note on optimal floodlight
illumination of stages . . . . . . . . . 121--123
Graham Farr and
Johannes Schmidt On the number of Go positions on lattice
graphs . . . . . . . . . . . . . . . . . 124--130
A. Kooshesh and
B. Ravikumar Efficient implementation of algorithms
for approximate exponentiation . . . . . 131--137
Ohad Lipsky and
Ely Porat Approximate matching in the $L_\infty$
metric . . . . . . . . . . . . . . . . . 138--140
Ohad Lipsky and
Ely Porat $L_1$ pattern matching lower bound . . . 141--143
Inge Li Gòrtz Asymmetric $k$-center with minimum
coverage . . . . . . . . . . . . . . . . 144--149
Sushmita Gupta Feedback arc set problem in bipartite
tournaments . . . . . . . . . . . . . . 150--154
Anonymous Editorial Board . . . . . . . . . . . . ??
Chris H. Hamilton and
Andrew Rau-Chaplin Compact Hilbert indices: Space-filling
curves for domains with unequal side
lengths . . . . . . . . . . . . . . . . 155--163
Gábor Salamon and
Gábor Wiener On finding spanning trees with few
leaves . . . . . . . . . . . . . . . . . 164--169
Frank Gurski Polynomial algorithms for protein
similarity search for restricted mRNA
structures . . . . . . . . . . . . . . . 170--176
Hsin-Hao Lai and
Gerard J. Chang and
Ko-Wei Lih On fully orientability of $2$-degenerate
graphs . . . . . . . . . . . . . . . . . 177--181
Szymon Grabowski and
Kimmo Fredriksson Bit-parallel string matching under
Hamming distance in $O(n \lceil m / w
\rceil)$ worst case time . . . . . . . . 182--187
Kuo-Si Huang and
Chang-Biau Yang and
Kuo-Tsung Tseng and
Hsing-Yen Ann and
Yung-Hsing Peng Efficient algorithms for finding
interleaving relationship between
sequences . . . . . . . . . . . . . . . 188--193
Markus Bläser and
Thomas Heynen and
Bodo Manthey Adding cardinality constraints to
integer programs with applications to
maximum satisfiability . . . . . . . . . 194--198
Pavlos S. Efraimidis The complexity of linear programming in
$(\gamma, \kappa)$-form . . . . . . . . 199--201
Sun-Yuan Hsieh and
Chih-Sheng Cheng Finding a maximum-density path in a tree
under the weight and length constraints 202--205
Yingqian Wang and
Huajing Lu and
Ming Chen A note on $3$-choosability of planar
graphs . . . . . . . . . . . . . . . . . 206--211
Anonymous Editorial Board . . . . . . . . . . . . ??
Stefano Crespi Reghizzi and
Matteo Pradella A CKY parser for picture grammars . . . 213--217
Costas S. Iliopoulos and
M. Sohel Rahman Faster index for property matching . . . 218--223
Dror Aiger and
Klara Kedem Applying graphics hardware to achieve
extremely fast geometric pattern
matching in two and three dimensional
transformation space . . . . . . . . . . 224--230
Xingjuan Cai and
Zhihua Cui and
Jianchao Zeng and
Ying Tan Dispersed particle swarm optimization 231--235
Ulrich Kühn Breaking the Shin--Shin--Rhee remotely
keyed encryption schemes . . . . . . . . 236--240
Amy Glen and
Aaron Lauve and
Franco V. Saliola A note on the Markoff condition and
central words . . . . . . . . . . . . . 241--244
Sreyash Kenkre and
Sundar Vishwanathan The common prefix problem on trees . . . 245--248
A. Álvarez and
S. Arévalo and
V. Cholvi and
A. Fernández and
E. Jiménez On the interconnection of message
passing systems . . . . . . . . . . . . 249--254
Anonymous Editorial Board . . . . . . . . . . . . ??
Krishnendu Chatterjee and
Thomas A. Henzinger Reduction of stochastic parity to
stochastic mean-payoff games . . . . . . 1--7
Joachim Biskup and
David W. Embley and
Jan-Hendrik Lochner Reducing inference control to access
control for normalized database schemas 8--12
Costas S. Iliopoulos and
M. Sohel Rahman New efficient algorithms for the LCS and
constrained LCS problems . . . . . . . . 13--18
Jyh-Jian Sheu and
Wen-Tzeng Huang and
Chin-Hsing Chen Strong diagnosability of regular
networks under the comparison model . . 19--25
Weiping He and
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 $\log \log N$-competitiveness
by splaying . . . . . . . . . . . . . . 37--43
Anonymous Editorial Board . . . . . . . . . . . . ??
Torben Amtoft Slicing for modern program structures: a
theory for eliminating irrelevant loops 45--51
Banghe Li and
Yuefeng Shen and
Bo Li A new algorithm for computing the
minimum Hausdorff distance between two
point sets on a line under translation 52--58
Meijie Ma and
Guizhen Liu and
Jun-Ming Xu The super connectivity of augmented
cubes . . . . . . . . . . . . . . . . . 59--63
Lun-Min Shih and
Chieh-Feng Chiang and
Lih-Hsing Hsu and
Jimmy J. M. Tan Strong Menger connectivity with
conditional faults on the class of
hypercube-like networks . . . . . . . . 64--69
Feifeng Zheng and
Yinfeng Xu and
E. Zhang How much can lookahead help in online
single machine scheduling . . . . . . . 70--74
Maxime Crochemore and
Lucian Ilie Computing Longest Previous Factor in
linear time and applications . . . . . . 75--80
Jiong Guo and
Rolf Niedermeier and
Johannes Uhlmann Two fixed-parameter algorithms for
Vertex Covering by Paths on Trees . . . 81--86
Anonymous Editorial Board . . . . . . . . . . . . ??
Stephan Westphal A note on the $k$-Canadian Traveller
Problem . . . . . . . . . . . . . . . . 87--89
S\`everine Bérard and
Cedric Chauve and
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 and
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 and
Cédric Meuter and
Laurent Van Begin On the complexity of partial order trace
model checking . . . . . . . . . . . . . 120--126
Adnan Mohamed and
R. S. Ramakrishna Linear election in pancake graphs . . . 127--131
Anonymous Editorial Board . . . . . . . . . . . . ??
Hanna Furma\'nczyk and
Adrian Kosowski and
Pawe\l \.Zyli\'nski A note on mixed tree coloring . . . . . 133--135
Gautam K. Das and
Subhas C. Nandy Weighted broadcast in linear radio
networks . . . . . . . . . . . . . . . . 136--143
Josep Díaz and
Zvi Lotker and
Maria Serna The distant-$2$ chromatic number of
random proximity and random geometric
graphs . . . . . . . . . . . . . . . . . 144--148
Attila Bernáth and
Gwenaël Joret Well-balanced orientations of mixed
graphs . . . . . . . . . . . . . . . . . 149--151
Jared Saia and
Maxwell Young Reducing communication costs in robust
peer-to-peer networks . . . . . . . . . 152--158
GaoJun Fan and
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 and
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
Anonymous Editorial Board . . . . . . . . . . . . ??
Tetsuo Kurosaki Direct definition of a ternary infinite
square-free sequence . . . . . . . . . . 175--179
Sébastien Collette and
Liliana Cucu and
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 and
Karol Suchan and
Ioan Todinca Minimal proper interval completions . . 195--202
Zeev Nutov and
Daniel Reichman Approximating maximum satisfiable
subsystems of linear equations of
bounded width . . . . . . . . . . . . . 203--207
Ronen Gradwohl and
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
Anonymous Editorial Board . . . . . . . . . . . . ??
Francisco Chicano and
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 and
Paulo S. L. M. Barreto and
Décio L. Gazzoni Filho Rotation symmetry in algebraically
generated cryptographic substitution
tables . . . . . . . . . . . . . . . . . 246--250
Orestis A. Telelis and
Vassilis Zissimopoulos Dynamic bottleneck optimization for
$k$-edge and $2$-vertex connectivity . . 251--257
Aygul Mamut and
Elkin Vumar Vertex vulnerability parameters of
Kronecker products of complete graphs 258--262
Anonymous Editorial Board . . . . . . . . . . . . ??
Fanica Gavril Minimum weight feedback vertex sets in
circle graphs . . . . . . . . . . . . . 1--6
Frank Pok Man Chu A simple linear time certifying
LBFS-based algorithm for recognizing
trivially perfect graphs and their
complements . . . . . . . . . . . . . . 7--12
Pedro García and
Manuel Vázquez de Parga and
Damián López On the efficient construction of
quasi-reversible automata for reversible
languages . . . . . . . . . . . . . . . 13--17
Pao-Lien Lai and
Hong-Chun Hsu The two-equal-disjoint path cover
problem of Matching Composition Network 18--23
Jianxin Wang and
Jianer Chen and
Min Huang An improved lower bound on approximation
algorithms for the Closest Substring
problem . . . . . . . . . . . . . . . . 24--28
Michael Segal Fast algorithm for multicast and data
gathering in wireless networks . . . . . 29--33
Artur Alves Pessoa A note on the construction of error
detecting/correcting prefix codes . . . 34--38
Shai Gutner Elementary approximation algorithms for
prize collecting Steiner tree problems 39--44
Anonymous Editorial Board . . . . . . . . . . . . ??
Justie Su-Tzu Juan and
Chun-Ming Huang and
I-fan Sun The strong distance problem on the
Cartesian product of graphs . . . . . . 45--51
Jorge Almeida and
Marc Zeitoun Description and analysis of a bottom-up
DFA minimization algorithm . . . . . . . 52--59
K. R. Duffy and
N. O'Connell and
A. Sapozhnikov Complexity analysis of a decentralised
graph colouring algorithm . . . . . . . 60--63
Yvonne Bleischwitz and
Florian Schoppmann New efficiency results for makespan cost
sharing . . . . . . . . . . . . . . . . 64--70
Jean-Baptiste Yun\`es A $4$-states algebraic solution to
linear cellular automata synchronization 71--75
Mario A. Lopez and
Shlomo Reisner Hausdorff approximation of $3$D convex
polytopes . . . . . . . . . . . . . . . 76--82
Kyung-Ah Shim Rogue-key attacks on the
multi-designated verifiers signature
scheme . . . . . . . . . . . . . . . . . 83--86
Anonymous Editorial Board . . . . . . . . . . . . ??
Jun Yan and
Jian Zhang An efficient method to generate feasible
paths for basis path testing . . . . . . 87--92
Joanna Skowronek-Kaziów $1,2$ Conjecture --- the multiplicative
version . . . . . . . . . . . . . . . . 93--95
Sören Laue and
Domagoj Matijevi\'c Approximating $k$-hop minimum spanning
trees in Euclidean metrics . . . . . . . 96--101
Haihui Zhang and
Zhiren Sun On $3$-choosability of planar graphs
without certain cycles . . . . . . . . . 102--106
Mickaël Montassier and
André Raspaud and
Weifan Wang and
Yingqian Wang A relaxation of Havel's $3$-color
problem . . . . . . . . . . . . . . . . 107--109
Jung-Sheng Fu Conditional fault Hamiltonicity of the
complete graph . . . . . . . . . . . . . 110--113
Lawrence S. Moss Confusion of memory . . . . . . . . . . 114--119
Joseph S. B. Mitchell and
Valentin Polishchuk Minimum-perimeter enclosures . . . . . . 120--124
François Delbot and
Christian Laforest A better list heuristic for vertex cover 125--127
John S. Fitzgerald and
Cliff B. Jones The connection between two ways of
reasoning about partial functions . . . 128--132
Anonymous Editorial Board . . . . . . . . . . . . ??
Orr Dunkelman and
Nathan Keller Treatment of the initial value in
Time-Memory-Data Tradeoff attacks on
stream ciphers . . . . . . . . . . . . . 133--137
Timothy M. Chan Well-separated pair decomposition in
linear time? . . . . . . . . . . . . . . 138--141
Hsin-Wen Wei and
Kwei-Jay Lin and
Wan-Chen Lu and
Wei-Kuan Shih Generalized rate monotonic
schedulability bounds using relative
period ratios . . . . . . . . . . . . . 142--148
Meena Mahajan and
Jayalal Sarma M. N. Rigidity of a simple extended lower
triangular matrix . . . . . . . . . . . 149--153
Mathieu Liedloff Finding a dominating set on bipartite
graphs . . . . . . . . . . . . . . . . . 154--157
Yi-Hsiung Chao and
Shun-Shii Lin and
Kwei-Jay Lin Schedulability issues for EDZL
scheduling on real-time multiprocessor
systems . . . . . . . . . . . . . . . . 158--164
M. L. Chiang and
S. C. Wang and
L. Y. Tseng The incremental agreement . . . . . . . 165--170
Chung-Meng Lee and
Jimmy J. M. Tan and
Lih-Hsing Hsu Embedding Hamiltonian paths in
hypercubes with a required vertex in a
fixed position . . . . . . . . . . . . . 171--176
Subhashis Majumder and
Bhargab B. Bhattacharya On the density and discrepancy of a $2$D
point set with applications to thermal
analysis of VLSI chips . . . . . . . . . 177--182
Gustavo M. D. Vieira and
Luiz E. Buzato On the coordinator's rule for Fast Paxos 183--187
Takunari Miyazaki On the asymmetric complexity of the
group-intersection problem . . . . . . . 188--193
Esther M. Arkin and
Joseph S. B. Mitchell and
Jack Snoeyink Capturing crossings: Convex hulls of
segment and plane intersections . . . . 194--197
Anonymous Editorial Board . . . . . . . . . . . . ??
Giorgio Ausiello and
Vincenzo Bonifaci and
Luigi Laura The online Prize-Collecting Traveling
Salesman Problem . . . . . . . . . . . . 199--204
Wen-Qing Wang and
Xie-Bin Chen A fault-free Hamiltonian cycle passing
through prescribed edges in a hypercube
with faulty edges . . . . . . . . . . . 205--210
Haibin Shen and
Yier Jin Low complexity bit parallel multiplier
for $\mathrm{GF}(2^m)$ generated by
equally-spaced trinomials . . . . . . . 211--215
K. De Loof and
B. De Baets and
H. De Meyer On the random generation of monotone
data sets . . . . . . . . . . . . . . . 216--220
José M. Cañete-Valdeón and
Fernando Enríquez and
Javier Ortega and
Ernesto Veláquez Clarifying the semantics of value in use
cases through Jackson's Problem Frames 221--229
Daniel Andrén and
Lars Hellström and
Klas Markström Fast multiplication of matrices over a
finitely generated semiring . . . . . . 230--234
Kai Engelhardt and
Yoram Moses Single-bit messages are insufficient for
data link over duplicating channels . . 235--239
Michael H. Goldwasser and
Arundhati Bagchi Misra A simpler competitive analysis for
scheduling equal-length jobs on one
machine with restarts . . . . . . . . . 240--245
Behrooz Parhami On isomorphisms and similarities between
generalized Petersen networks and
periodically regular chordal rings . . . 246--251
Li Sun and
Fuji Zhang and
Jianguo Qian Multi-hop all-to-all optical routings in
Cartesian product networks . . . . . . . 252--256
Min-Sheng Lin and
Yung-Jui Chen Linear time algorithms for counting the
number of minimal vertex covers with
minimum/maximum size in an interval
graph . . . . . . . . . . . . . . . . . 257--264
Anonymous Editorial Board . . . . . . . . . . . . ??
Y. Boichut and
P.-C. Héam A theoretical limit for safety
verification techniques with regular
fix-point computations . . . . . . . . . 1--2
Xiang Zhou Ehrenfeucht--Fra\"\issé games in finite
set theory . . . . . . . . . . . . . . . 3--9
Henning Bordihn and
Markus Holzer A note on cooperating distributed
grammar systems working in combined
modes . . . . . . . . . . . . . . . . . 10--14
Reuven Cohen and
Liran Katzir The Generalized Maximum Coverage Problem 15--22
Manfred Droste and
Jacques Sakarovitch and
Heiko Vogler Weighted automata with discounting . . . 23--28
Maria Liazi and
Ioannis Milis and
Vassilis Zissimopoulos A constant approximation algorithm for
the densest $k$-subgraph problem on
chordal graphs . . . . . . . . . . . . . 29--32
Sung-Hwa Lim and
Byoung-Hoon Lee and
Jai-Hoon Kim Diversity and fault avoidance for
dependable replication systems . . . . . 33--37
Ulrich M. Schwarz Online scheduling on semi-related
machines . . . . . . . . . . . . . . . . 38--40
Vladimir Yanovsky Approximation algorithm for coloring of
dotted interval graphs . . . . . . . . . 41--44
Anonymous Editorial Board . . . . . . . . . . . . ??
Kai Puolamäki and
Sami Hanhijärvi and
Gemma C. Garriga An approximation ratio for biclustering 45--49
Eduardo Tavares and
Paulo Maciel and
Bruno Silva and
Meuse N. Oliveira, Jr. Hard real-time tasks' scheduling
considering voltage scaling, precedence
and exclusion relations . . . . . . . . 50--59
Valentin Ziegler Approximation algorithms for restricted
Bayesian network structures . . . . . . 60--63
Sebastian Czerwi\'nski and
Jaros\law Grytczuk Invisible runners in finite fields . . . 64--67
Tomá\vs Masopust Descriptional complexity of
multi-parallel grammars . . . . . . . . 68--70
Stefan Göller Reachability on prefix-recognizable
graphs . . . . . . . . . . . . . . . . . 71--74
R\uazvan Diaconescu A categorical study on the finiteness of
specifications . . . . . . . . . . . . . 75--80
Sun-Yuan Hsieh A note on cycle embedding in folded
hypercubes with faulty elements . . . . 81--81
Pascal Ochem and
Alexandre Pinlou Oriented colorings of partial $2$-trees 82--86
Anonymous Editorial Board . . . . . . . . . . . . ??
De-Qiang Wang and
Yu-Peng Wen and
Ke-Lun Wang A smaller planar graph without $4$-,
$5$-cycles and intersecting triangles
that is not $3$-choosable . . . . . . . 87--89
Juan Liu and
Jixiang Meng Super-connected and super-arc-connected
Cartesian product of digraphs . . . . . 90--93
Gabriela Minetti and
Enrique Alba and
Gabriel Luque Seeding strategies and recombination
operators for solving the DNA fragment
assembly problem . . . . . . . . . . . . 94--100
Marjan Heri\vcko and
Ale\vs \vZivkovi\vc and
Ivan Rozman An approach to optimizing software
development team size . . . . . . . . . 101--106
Kung-Jui Pai and
Jou-Ming Chang and
Yue-Li Wang A Note on ``An improved upper bound on
the queuenumber of the hypercube'' . . . 107--109
Li Jiao A note on regular Petri nets . . . . . . 110--114
Vesa Halava and
Tero Harju and
Mika Hirvensalo and
Juhani Karhumäki Post Correspondence Problem for short
words . . . . . . . . . . . . . . . . . 115--118
Akka Zemmari On handshakes in random graphs . . . . . 119--123
Sylvain Lavallée $\mathbb{N}$-rationality of a certain
class of formal series . . . . . . . . . 124--126
Brad Long Managing module dependencies to
facilitate continuous testing . . . . . 127--131
Salim Haddadi and
Zoubir Layouni Consecutive block minimization is
$1.5$-approximable . . . . . . . . . . . 132--135
Rajesh Bordawekar and
Oded Shmueli An algorithm for partitioning trees
augmented with sibling edges . . . . . . 136--142
Julia Böttcher and
Dan Vilenchik On the tractability of coloring
semirandom graphs . . . . . . . . . . . 143--149
Raquel Viaña Quick encoding of plane graphs in
$\log_2 14$ bits per edge . . . . . . . 150--154
Hiroshi Fujiwara and
Kazuo Iwama and
Kouki Yonezawa Online chasing problems for regular
polygons . . . . . . . . . . . . . . . . 155--159
Sergio Rajsbaum and
Michel Raynal and
Corentin Travers An impossibility about failure detectors
in the iterated immediate snapshot model 160--164
Joanna Skowronek-Kaziów Some digraphs arising from number theory
and remarks on the zero-divisor graph of
the ring $Z_n$ . . . . . . . . . . . . . 165--169
Anonymous Editorial Board . . . . . . . . . . . . ??
Min Ji and
T. C. E. Cheng An FPTAS for parallel-machine scheduling
under a grade of service provision to
minimize makespan . . . . . . . . . . . 171--174
Claire Mathieu and
Charalampos Papamanthou Distortion lower bounds for line
embeddings . . . . . . . . . . . . . . . 175--178
Rainer Steinwandt and
Viktória I. Villányi A one-time signature using run-length
encoding . . . . . . . . . . . . . . . . 179--185
Pierre Charbit and
Michel Habib and
Vincent Limouzy and
Fabien de Montgolfier and
Mathieu Raffinot and
Michaël Rao A note on computing set overlap classes 186--191
Jyhjong Lin A conceptual model for negotiating in
service-oriented environments . . . . . 192--203
Changsheng Zhang and
Jigui Sun and
Xingjun Zhu and
Qingyun Yang An improved particle swarm optimization
algorithm for flowshop scheduling
problem . . . . . . . . . . . . . . . . 204--209
Prosenjit Bose and
Hua Guo and
Evangelos Kranakis and
Anil Maheshwari and
Pat Morin and
Jason Morrison and
Michiel Smid and
Yihui Tang On the false-positive rate of Bloom
filters . . . . . . . . . . . . . . . . 210--213
Stanley P. Y. Fung Lower bounds on online deadline
scheduling with preemption penalties . . 214--218
Pauli Miettinen On the Positive--Negative Partial Set
Cover problem . . . . . . . . . . . . . 219--221
Volker Heun Analysis of a modification of Gusfield's
recursive algorithm for reconstructing
ultrametric trees . . . . . . . . . . . 222--225
Tracy Grauman and
Stephen G. Hartke and
Adam Jobson and
Bill Kinnersley and
Douglas B. West and
Lesley Wiglesworth and
Pratik Worah and
Hehui Wu The hub number of a graph . . . . . . . 226--228
Yasuhiko Takenaga and
Shigeru Arai PSPACE-completeness of an escape problem 229--233
Ricardo dos Santos Carvalho and
Carlile Lavor and
Fábio Protti Extending the geometric build-up
algorithm for the molecular distance
geometry problem . . . . . . . . . . . . 234--237
Martin Kochol and
Nad'a Krivo\vnáková and
Silvia Smejová and
Katarína \vSranková Complexity of approximation of
$3$-edge-coloring of graphs . . . . . . 238--241
P.-C. Héam A note on partially ordered tree
automata . . . . . . . . . . . . . . . . 242--246
Mitre C. Dourado and
Min Chih Lin and
Fábio Protti and
Jayme L. Szwarcfiter Improved algorithms for recognizing
$p$-Helly and hereditary $p$-Helly
hypergraphs . . . . . . . . . . . . . . 247--250
Dekel Tsur Faster algorithms for guided tree edit
distance . . . . . . . . . . . . . . . . 251--254
Anonymous Editorial Board . . . . . . . . . . . . ??
Louis Esperet and
Arnaud Labourel and
Pascal Ochem On induced-universal graphs for the
class of bounded-degree graphs . . . . . 255--260
Jung-Sheng Fu Fault-free cycles in folded hypercubes
with more faulty elements . . . . . . . 261--263
Sándor Vágvölgyi Murg term rewrite systems . . . . . . . 264--272
Christian Boulinier and
Ajoy K. Datta and
Lawrence L. Larmore and
Franck Petit Space efficient and time optimal
distributed BFS tree construction . . . 273--278
David Galindo and
Javier Herranz On the security of public key
cryptosystems with a double decryption
mechanism . . . . . . . . . . . . . . . 279--283
Luca Aceto and
Silvio Capobianco and
Anna Ingolfsdottir and
Bas Luttik The equational theory of prebisimilarity
over basic CCS with divergence . . . . . 284--289
Vesa Halava and
Tero Harju and
Tomi Kärki Square-free partial words . . . . . . . 290--292
Bishnu Bhattacharyya and
Frank Dehne Using spine decompositions to
efficiently solve the length-constrained
heaviest path problem for trees . . . . 293--297
Rod Downey and
Noam Greenberg Turing degrees of reals of positive
effective packing dimension . . . . . . 298--303
Álvar Ibeas Martín On the period of the Naor--Reingold
sequence . . . . . . . . . . . . . . . . 304--307
Martin Lange A purely model-theoretic proof of the
exponential succinctness gap between CTL
$^+$ and CTL . . . . . . . . . . . . . . 308--312
Heikki Hyyrö Improving the bit-parallel NFA of
Baeza-Yates and Navarro for approximate
string matching . . . . . . . . . . . . 313--319
Maxime Crochemore and
Costas S. Iliopoulos and
M. Sohel Rahman Optimal prefix and suffix queries on
texts . . . . . . . . . . . . . . . . . 320--325
Chia-Jui Lai and
Chang-Hsiung Tsai Embedding a family of meshes into
twisted cubes . . . . . . . . . . . . . 326--330
Jinsong Tan A note on the inapproximability of
correlation clustering . . . . . . . . . 331--335
Fokko J. van de Bult and
Gerhard J. Woeginger The problem of the moody chess players 336--337
Anonymous Editorial Board . . . . . . . . . . . . ??
Taek-Young Youn and
Young-Ho Park and
Changhan Kim and
Jongin Lim Weakness in a RSA-based password
authenticated key exchange protocol . . 339--342
Arindam Karmakar and
Sasanka Roy and
Sandip Das Fast computation of smallest enclosing
circle with center on a query line
segment . . . . . . . . . . . . . . . . 343--346
Bin Liu and
Jianfeng Hou and
Guizhen Liu List edge and list total colorings of
planar graphs without short cycles . . . 347--351
Travis Gagie Dynamic asymmetric communication . . . . 352--355
Fethi Jarray and
Marie-Christine Costa and
Christophe Picouleau Complexity results for the horizontal
bar packing problem . . . . . . . . . . 356--359
Hsing-Yen Ann and
Chang-Biau Yang and
Chiou-Ting Tseng and
Chiou-Yi Hor A fast and simple algorithm for
computing the longest common subsequence
of run-length encoded strings . . . . . 360--364
Zvi Lotker and
Boaz Patt-Shamir and
Dror Rawitz Ski rental with two general options . . 365--368
Xiaotie Deng and
Ye Du The computation of approximate
competitive equilibrium is PPAD-hard . . 369--373
Peter Massuthe and
Alexander Serebrenik and
Natalia Sidorova and
Karsten Wolf Can I find a partner? Undecidability of
partner existence for open nets . . . . 374--378
Yusu Wang Approximating nearest neighbor among
triangles in convex position . . . . . . 379--385
Shiying Wang and
Shangwei Lin $\lambda^{\prime}$-optimal digraphs . . 386--389
Ariel D. Procaccia A note on the query complexity of the
Condorcet winner problem . . . . . . . . 390--393
Qiang Dong and
Xiaofan Yang and
Juan Zhao Embedding a family of disjoint
multi-dimensional meshes into a crossed
cube . . . . . . . . . . . . . . . . . . 394--397
Xuegong Tan and
Shun-Zheng Yu and
Jin Han Park A note about some properties of BC
graphs . . . . . . . . . . . . . . . . . 398--401
Petr Gregor and
Tomá\vs Dvo\vrák Path partitions of hypercubes . . . . . 402--406
Amos Israeli and
Oran Sharon An approximation algorithm for
sequential rectangle placement . . . . . 407--411
Anna Fiedorowicz and
Mariusz Ha\luszczak and
Narayanan Narayanan About acyclic edge colourings of planar
graphs . . . . . . . . . . . . . . . . . 412--417
Travis Gagie Sorting streamed multisets . . . . . . . 418--421
Anonymous Editorial Board . . . . . . . . . . . . ??
Jong-Won Roh and
Byoung-Kee Yi Efficient indexing of interval time
sequences . . . . . . . . . . . . . . . 1--12
Olivier Gauwin and
Joachim Niehren and
Yves Roos Streaming tree automata . . . . . . . . 13--17
Youngjoong Ko and
Hongkuk An and
Jungyun Seo Pseudo-relevance feedback and
statistical query expansion for Web
snippet generation . . . . . . . . . . . 18--22
J. Nagy-György and
Cs. Imreh Online hypergraph coloring . . . . . . . 23--26
Sumit Ganguly and
Anirban Majumder Deterministic K-set structure . . . . . 27--31
Leah Epstein and
Asaf Levin Asymptotic fully polynomial
approximation schemes for variants of
open-end bin packing . . . . . . . . . . 32--37
Cor A. J. Hurkens and
Rudi A. Pendavingh and
Gerhard J. Woeginger The Magnus--Derek game revisited . . . . 38--40
Beate Bollig A note on the size of OBDDs for the
graph of integer multiplication . . . . 41--43
Shakhar Smorodinsky A note on the online First-Fit algorithm
for coloring $k$-inductive graphs . . . 44--45
J. Andrés Montoya The parameterized complexity of
probability amplification . . . . . . . 46--53
Martin Held and
Joseph S. B. Mitchell Triangulating input-constrained planar
point sets . . . . . . . . . . . . . . . 54--56
Tetsuo Asano Online uniformity of integer points on a
line . . . . . . . . . . . . . . . . . . 57--60
Selim G. Akl and
Kamrul Islam and
Henk Meijer Planar tree transformation: Results and
counterexample . . . . . . . . . . . . . 61--67
Rodney G. Downey and
Michael R. Fellows and
Catherine McCartin and
Frances Rosamond Parameterized approximation of
dominating set problems . . . . . . . . 68--70
Rafael Dueire Lins Cyclic reference counting . . . . . . . 71--78
Mikhail J. Atallah and
Greg N. Frederickson and
Ashish Kundu A tree-covering problem arising in
integrity of tree-structured data . . . 79--82
Luca Aceto and
Anna Ingolfsdottir On the expressibility of priority . . . 83--85
Anonymous Editorial Board . . . . . . . . . . . . ??
Mark de Berg and
Shripad Thite Cache-oblivious selection in sorted X +
Y matrices . . . . . . . . . . . . . . . 87--92
J. Mark Keil and
Tzvetalin S. Vassilev The relative neighbourhood graph is a
part of every 30$^\circ$-triangulation 93--97
Roberto Baldoni and
François Bonnet and
Alessia Milani and
Michel Raynal Anonymous graph exploration without
collision by mobile robots . . . . . . . 98--103
Taolue Chen and
Wan Fokkink and
Rob van Glabbeek Ready to preorder: The case of weak
process semantics . . . . . . . . . . . 104--111
Ruei-Yu Wu and
Gen-Huey Chen and
Jung-Sheng Fu and
Gerard J. Chang Finding cycles in hierarchical hypercube
networks . . . . . . . . . . . . . . . . 112--115
Hwei-Jen Lin and
Hung-Hsuan Wu Efficient geometric measure of music
similarity . . . . . . . . . . . . . . . 116--120
Palash Sarkar A general mixing strategy for the
ECB-Mix-ECB mode of operation . . . . . 121--123
Clemens Huemer and
Ferran Hurtado and
Julian Pfeifle The rotation graph of $k$-ary trees is
Hamiltonian . . . . . . . . . . . . . . 124--129
Rui Li and
Jixiang Meng Reversals Cayley graphs of symmetric
groups . . . . . . . . . . . . . . . . . 130--132
Aravind Srinivasan A note on the distribution of the number
of prime factors of the integers . . . . 133--135
Emanuele G. Fusco and
Andrzej Pelc Acknowledged broadcasting in ad hoc
radio networks . . . . . . . . . . . . . 136--141
Bahram Sadeghi Bigham and
Ali Mohades and
Lidia Ortega Dynamic polar diagram . . . . . . . . . 142--146
Chia-Jui Lai and
Chang-Hsiung Tsai On embedding cycles into faulty
dual-cubes . . . . . . . . . . . . . . . 147--150
V. Cholvi Stability bounds in networks with
dynamic link capacities . . . . . . . . 151--154
Johann L. Hurink and
Tim Nieberg Approximating minimum independent
dominating sets in wireless networks . . 155--160
Hsin-Hao Su and
Chin Lung Lu and
Chuan Yi Tang An improved algorithm for finding a
length-constrained maximum-density
subtree in a tree . . . . . . . . . . . 161--164
Tatsuya Akutsu and
Daiji Fukagawa and
Atsuhiro Takasu Improved approximation of the largest
common subtree of two unordered trees of
bounded height . . . . . . . . . . . . . 165--170
Anonymous Editorial Board . . . . . . . . . . . . ??
Chih-Huai Cheng and
Hsiao-Fei Liu and
Kun-Mao Chao Optimal algorithms for the
average-constrained maximum-sum segment
problem . . . . . . . . . . . . . . . . 171--174
Valentin Ziegler Approximating optimum branchings in
linear time . . . . . . . . . . . . . . 175--178
Edo Liberty and
Steven W. Zucker The Mailman algorithm: A note on
matrix--vector multiplication . . . . . 179--182
Mira Gonen and
Yuval Shavitt A $\Theta(\log n)$-approximation for the
set cover problem with set ownership . . 183--186
Markus Bläser and
Moritz Hardt and
Richard J. Lipton and
Nisheeth K. Vishnoi Deterministically testing sparse
polynomial identities of unbounded
degree . . . . . . . . . . . . . . . . . 187--192
Sarah Novotny and
Juan Ortiz and
Darren A. Narayan Minimal $k$-rankings and the rank number
of $P_n^2$ . . . . . . . . . . . . . . . 193--198
Jing Huang and
Haina Sun and
Weifan Wang and
Dong Chen (2,1)-Total labelling of trees with
sparse vertices of maximum degree . . . 199--203
Xin Han and
He Guo and
Dawei Yin and
Yong Zhang A note on on-line broadcast scheduling
with deadlines . . . . . . . . . . . . . 204--207
Sanjay Jain On some open problems in reflective
inductive inference . . . . . . . . . . 208--211
Anonymous Editorial Board . . . . . . . . . . . . ??
Víctor Dalmau There are no pure relational width $2$
constraint satisfaction problems . . . . 213--218
Esther M. Arkin and
Sang Won Bae and
Alon Efrat and
Kazuya Okamoto and
Joseph S. B. Mitchell and
Valentin Polishchuk Geometric stable roommates . . . . . . . 219--224
Holger Petersen and
Szymon Grabowski Range mode and range median queries in
constant time and sub-quadratic space 225--228
Pascal Schweitzer Using the incompressibility method to
obtain local lemma results for
Ramsey-type problems . . . . . . . . . . 229--232
Krzysztof Majewski and
Nicholas Pippenger Attribute estimation and testing
quasi-symmetry . . . . . . . . . . . . . 233--237
Mukul S. Bansal and
David Fernández-Baca Computing distances between partial
rankings . . . . . . . . . . . . . . . . 238--241
Leszek G\kasieniec and
Miros\law Kowaluk and
Andrzej Lingas Faster multi-witnesses for Boolean
matrix multiplication . . . . . . . . . 242--247
Hongbo Hua and
Yaoping Hou On graphs with the third largest number
of maximal independent sets . . . . . . 248--253
Virginia Vassilevska Efficient algorithms for clique problems 254--257
Anonymous Editorial Board . . . . . . . . . . . . ??
Noam Livne A note on #P-completeness of
NP-witnessing relations . . . . . . . . 259--261
Adam Kasperski and
Pawe\l Zieli\'nski On the approximability of minmax
(regret) network optimization problems 262--266
Tomás Feder and
Carlos Subi Nearly tight bounds on the number of
Hamiltonian circuits of the hypercube
and generalizations . . . . . . . . . . 267--272
Chaim Linhart and
Ron Shamir Matching with don't-cares and a small
number of mismatches . . . . . . . . . . 273--277
Jiuchuan Jiang and
Xiaojun Xia Prominence convergence in the collective
synchronization of situated multi-agents 278--285
S. Jukna A nondeterministic space-time tradeoff
for linear codes . . . . . . . . . . . . 286--289
Ananya Das and
Charles Martel Stochastic shortest path with unlimited
hops . . . . . . . . . . . . . . . . . . 290--295
Yue Li and
Joe Sawada Gray codes for reflectable languages . . 296--300
Anonymous Editorial Board . . . . . . . . . . . . ??
Fabrizio Frati and
Markus Geyer and
Michael Kaufmann Planar packing of trees and spider trees 301--307
Dariusz R. Kowalski and
Micha\l Strojnowski Gossiping by processors prone to
omission failures . . . . . . . . . . . 308--314
Ryan Williams Finding paths of length $k$ in
$O^*(2^k)$ time . . . . . . . . . . . . 315--318
Vadim Lozin and
Raffaele Mosca Maximum independent sets in subclasses
of P $_5$-free graphs . . . . . . . . . 319--324
Sebastian Dörn and
Thomas Thierauf The quantum query complexity of the
determinant . . . . . . . . . . . . . . 325--328
A. Karim Abu-Affash and
Matthew J. Katz Improved bounds on the average distance
to the Fermat--Weber center of a convex
object . . . . . . . . . . . . . . . . . 329--333
Abraham P. Punnen and
Ruonan Zhang Bottleneck flows in unit capacity
networks . . . . . . . . . . . . . . . . 334--338
Anonymous Editorial Board . . . . . . . . . . . . ??
W. Fernandez de la Vega and
Zsolt Tuza Groupies in random graphs . . . . . . . 339--340
Gerhard J. Woeginger A comment on parallel-machine scheduling
under a grade of service provision to
minimize makespan . . . . . . . . . . . 341--342
Jiansheng Cai and
Jianfeng Hou and
Xia Zhang and
Guizhen Liu Edge-choosability of planar graphs
without non-induced 5-cycles . . . . . . 343--346
Daegun Ma and
Jin Hong Success probability of the Hellman
trade-off . . . . . . . . . . . . . . . 347--351
Zvi Gotthilf and
Moshe Lewenstein Improved algorithms for the $k$ simple
shortest paths and the replacement paths
problems . . . . . . . . . . . . . . . . 352--355
Antti Ukkonen and
Kai Puolamäki and
Aristides Gionis and
Heikki Mannila A randomized approximation algorithm for
computing bucket orders . . . . . . . . 356--359
Christian Cachin and
Idit Keidar and
Alexander Shraer Fork sequential consistency is blocking 360--364
Venkatesan T. Chakaravarthy and
Sambuddha Roy Approximating maximum weight
$K$-colorable subgraphs in chordal
graphs . . . . . . . . . . . . . . . . . 365--368
Manzhan Gu and
Xiwen Lu Preemptive stochastic online scheduling
on two uniform machines . . . . . . . . 369--375
Uwe Bubeck and
Hans Kleine Büning A new 3-CNF transformation by
parallel-serial graphs . . . . . . . . . 376--379
Anonymous Editorial Board . . . . . . . . . . . . ??
Panagiotis Antonellis and
Christos Makris and
Nikos Tsirakis Algorithms for clustering clickstream
data . . . . . . . . . . . . . . . . . . 381--385
S. Abravaya and
D. Berend Multi-dimensional dynamic facility
location and fast computation at query
points . . . . . . . . . . . . . . . . . 386--390
J. Spoerhase and
H.-C. Wirth An $O(n (\log n)^2 / \log \log n)$
algorithm for the single maximum
coverage location or the $(1,
X_p)$-medianoid problem on trees . . . . 391--394
Xie-Bin Chen Some results on topological properties
of folded hypercubes . . . . . . . . . . 395--399
Zhengbing Bian and
Qian-Ping Gu 1.5-Approximation algorithm for weighted
maximum routing and wavelength
assignment on rings . . . . . . . . . . 400--404
Takayuki Nagoya New differential approximation algorithm
for $k$-customer vehicle routing problem 405--408
Jou-Ming Chang and
Ro-Yu Wu On the diameter of geometric path graphs
of points in convex position . . . . . . 409--413
Chuan-Min Lee and
Maw-Shang Chang Signed and minus clique-transversal
functions on graphs . . . . . . . . . . 414--417
Anonymous Editorial Board . . . . . . . . . . . . ??
Sanjeev Saxena Dominance made simple . . . . . . . . . 419--421
Dariusz Dereniowski Maximum vertex occupation time and inert
fugitive: Recontamination does help . . 422--426
Yufeng Wu An analytical upper bound on the minimum
number of recombinations in the history
of SNP sequences in populations . . . . 427--431
L. Sunil Chandran and
Anita Das and
Naveen Sivadasan On the cubicity of bipartite graphs . . 432--435
Etienne Birmelé and
François Delbot and
Christian Laforest Mean analysis of an online algorithm for
the vertex cover problem . . . . . . . . 436--439
S. Cabello and
M. Fort and
J. A. Sellar\`es Higher-order Voronoi diagrams on
triangulated surfaces . . . . . . . . . 440--445
Yilun Shang Connectivity in a random interval graph
with access points . . . . . . . . . . . 446--449
Chi-Jung Kuo and
Chiun-Chieh Hsu and
Hon-Ren Lin and
Kung-Kuei Lin An efficient algorithm for minimum
feedback vertex sets in rotator graphs 450--453
Eunsang Kim and
Kunsoo Park Improving multikey Quicksort for sorting
strings with many equal elements . . . . 454--459
Anonymous Editorial Board . . . . . . . . . . . . ??
Peter Brass Universal hash functions for an infinite
universe and hash trees . . . . . . . . 461--462
Serge Gaspers and
Margaret-Ellen Messinger and
Richard J. Nowakowski and
Pawe\l Pra\lat Clean the graph before you draw it! . . 463--467
M. A. Iwen and
C. V. Spencer A note on compressed sensing and the
complexity of matrix multiplication . . 468--471
W\vei Chén and
Wenhui Zhang A direct construction of polynomial-size
OBDD proof of pigeon hole problem . . . 472--477
Sasanka Roy and
Subhasis Bhattacharjee and
Sandip Das and
Subhas C. Nandy A new fast heuristic for labeling points 478--484
Ippei Koura and
Takao Ono and
Tomio Hirata A note on the Greedy algorithm for
finding independent sets of $C_k$-free
graphs . . . . . . . . . . . . . . . . . 485--489
Ryo Yoshinaka An elementary proof of a generalization
of double Greibach normal form . . . . . 490--492
Andrzej Lingas and
Eva-Marta Lundell Efficient approximation algorithms for
shortest cycles in undirected graphs . . 493--498
Beate Bollig On the size of (generalized) OBDDs for
threshold functions . . . . . . . . . . 499--503
Joong Chae Na and
Namhee Kim and
Jeong Seop Sim and
Dong Kyue Kim Improving on-line construction of
two-dimensional suffix trees for square
matrices . . . . . . . . . . . . . . . . 504--508
Balder ten Cate A note on the expressibility problem for
modal logics and star-free regular
expressions . . . . . . . . . . . . . . 509--513
Jean Marcel Pallo Weak associativity and restricted
rotation . . . . . . . . . . . . . . . . 514--517
Chi-Hung Tzeng and
Jehn-Ruey Jiang and
Shing-Tsaan Huang A self-stabilizing algorithm for the
maximum planarization problem in
complete bipartite networks . . . . . . 518--522
Anonymous Editorial Board . . . . . . . . . . . . ??
Vanesa Daza and
Javier Herranz and
Germán Sáez Flaws in some self-healing key
distribution schemes with revocation . . 523--526
Yanli Ren and
Dawu Gu Fully CCA2 secure identity based
broadcast encryption without random
oracles . . . . . . . . . . . . . . . . 527--533
Bruno Zanuttini and
Stanislav \vZivný A note on some collapse results of
valued constraints . . . . . . . . . . . 534--538
Erik Saule and
Denis Trystram Analyzing scheduling with transient
failures . . . . . . . . . . . . . . . . 539--542
Artur Je\.z and
Jakub \Lopusza\'nski On the two-dimensional cow search
problem . . . . . . . . . . . . . . . . 543--547
Milan R. Rapai\'c and
\vZeljko Kanovi\'c Time-varying PSO --- convergence
analysis, convergence-related
parameterization and new parameter
adjustment schemes . . . . . . . . . . . 548--552
Liuling Dai An aggressive algorithm for multiple
string matching . . . . . . . . . . . . 553--559
K. Viswanathan Iyer and
S. Prasanna A linear time algorithm for finding an
optimal degree-bounded subtree of an
edge-weighted tree . . . . . . . . . . . 560--562
Irene Fink and
Sven O. Krumke and
Stephan Westphal New lower bounds for online $k$-server
routing problems . . . . . . . . . . . . 563--567
Fabrizio Luccio and
Linda Pagli The Fermat star of binary trees . . . . 568--571
Manuel Bodirsky and
Gustav Nordh and
Timo von Oertzen Integer programming with 2-variable
equations and 1-variable inequalities 572--575
Christos Nomikos and
Panos Rondogiannis and
William W. Wadge Strong equivalence of logic programs
under the infinite-valued semantics . . 576--581
Paolo Detti A polynomial algorithm for the multiple
knapsack problem with divisible item
sizes . . . . . . . . . . . . . . . . . 582--584
Anonymous Editorial Board . . . . . . . . . . . . ??
Tung-Yang Ho and
Yuan-Kang Shih and
Jimmy J. M. Tan and
Lih-Hsing Hsu Conditional fault Hamiltonian
connectivity of the complete graph . . . 585--588
Damien Imbs and
Michel Raynal A note on atomicity: Boosting Test&Set to
solve consensus . . . . . . . . . . . . 589--591
Meijie Ma and
Xuegong Tan and
Jun-Ming Xu and
Guizhen Liu A note on ``The super connectivity of
augmented cubes'' . . . . . . . . . . . 592--593
Xie-Bin Chen On path bipancyclicity of hypercubes . . 594--598
Meirun Chen and
Xiaofeng Guo Adjacent vertex-distinguishing edge and
total chromatic numbers of hypercubes 599--602
Cheng He and
Yixun Lin and
Jinjiang Yuan A DP algorithm for minimizing makespan
and total completion time on a
series-batching machine . . . . . . . . 603--607
Kangbok Lee and
Joseph Y.-T. Leung and
Michael L. Pinedo A note on ``An approximation algorithm
for the load-balanced semi-matching
problem in weighted bipartite graphs'' 608--610
Thomas Studer Common knowledge does not have the Beth
property . . . . . . . . . . . . . . . . 611--614
Joanna Bauer and
Dag Haugland and
Di Yuan New results on the time complexity and
approximation ratio of the Broadcast
Incremental Power algorithm . . . . . . 615--619
Henk Meijer and
Yurai Núñez-Rodríguez and
David Rappaport An algorithm for computing simple
$k$-factors . . . . . . . . . . . . . . 620--625
Rebecca Smith and
Vincent Vatter The enumeration of permutations sortable
by pop stacks in parallel . . . . . . . 626--629
Sebastian Deorowicz An algorithm for solving the longest
increasing circular subsequence problem 630--634
Gerold Jäger and
Marcin Peczarski The number of pessimistic guesses in
Generalized Mastermind . . . . . . . . . 635--641
Valentin Polishchuk and
Jukka Suomela A simple local 3-approximation algorithm
for vertex cover . . . . . . . . . . . . 642--645
Anonymous Editorial Board . . . . . . . . . . . . ??
Hadas Shachnai and
Lisa Zhang and
Tomomi Matsui A note on generalized rank aggregation 647--651
Alina Carmen Cojocaru and
Igor E. Shparlinski On the embedding degree of reductions of
an elliptic curve . . . . . . . . . . . 652--654
Juan Liu and
Xing Chen and
Jixiang Meng Super restricted edge connected
Cartesian product graphs . . . . . . . . 655--659
George Davida and
Bruce Litow and
Guangwu Xu Fast arithmetics using Chinese
remaindering . . . . . . . . . . . . . . 660--662
Cong Tian and
Zhenhua Duan A note on stutter-invariant PLTL . . . . 663--667
Tommaso Bolognesi A pseudo-random network mobile automaton
with linear growth . . . . . . . . . . . 668--674
Michael T. Goodrich On the algorithmic complexity of the
Mastermind game with black-peg results 675--678
Arturo Carpi and
Valerio D'Alonzo On a word avoiding near repeats . . . . 679--682
Yingzhi Tian and
Jixiang Meng $\lambda_c$-Optimally half vertex
transitive graphs with regularity $k$ 683--686
Mohamed Abdo Efficient generation of the ideals of a
poset in Gray code order . . . . . . . . 687--689
Elad Horev and
Matthew J. Katz and
Roi Krakovski and
Maarten Löffler Polychromatic $4$-coloring of guillotine
subdivisions . . . . . . . . . . . . . . 690--694
Qi-yan Zhou and
San-yang Liu and
Qiang Zhu Local diagnosability of generic
star-pyramid graph . . . . . . . . . . . 695--699
Gilles Bertrand and
Michel Couprie and
Nicolas Passat A note on $3$-D simple points and
simple-equivalence . . . . . . . . . . . 700--704
Brian Alspach and
Matthew Dean Honeycomb toroidal graphs are Cayley
graphs . . . . . . . . . . . . . . . . . 705--708
Mohammadreza Jooyandeh and
Ali Mohades and
Maryam Mirzakhah Uncertain Voronoi diagram . . . . . . . 709--712
Hue-Ling Chen and
Ye-In Chang Spatial joins based on NA-trees . . . . 713--718
M. Abellanas and
S. Canales and
G. Hernández-Peñalver An ``Art Gallery Theorem'' for pyramids 719--721
Michael Orlov Optimized random number generation in an
interval . . . . . . . . . . . . . . . . 722--725
Wolfgang Mulzer A note on predecessor searching in the
pointer machine model . . . . . . . . . 726--729
Xuan Cai Linear kernelizations for restricted
$3$-Hitting Set problems . . . . . . . . 730--738
Gösta Grahne and
Alex Thomo Bounded regular path queries in
view-based data integration . . . . . . 739--744
Sang-il Oum Computing rank-width exactly . . . . . . 745--748
M. Arfi and
B. Ould M. Lemine and
C. Selmi Strategical languages of infinite words 749--753
Alin Bostan and
Éric Schost A simple and fast algorithm for
computing exponentials of power series 754--756
James K. Lan and
Victor W. Liu and
Chiuyuan Chen Improved upper and lower bounds on the
optimization of mixed chordal ring
networks . . . . . . . . . . . . . . . . 757--762
Anonymous Editorial Board . . . . . . . . . . . . ??
Volker Turau and
Bernd Hauck A self-stabilizing algorithm for
constructing weakly connected minimal
dominating sets . . . . . . . . . . . . 763--767
M. Abellanas and
A. L. Bajuelos and
I. Matos $2$-Covered paths by a set of antennas
with minimum power transmission range 768--773
Tomás Feder and
Rajeev Motwani On the graph turnpike problem . . . . . 774--776
Kohji Tomita and
Haruhisa Kurokawa On the reachability of a version of
graph-rewriting system . . . . . . . . . 777--782
Wenguang Chen and
Wenfei Fan and
Shuai Ma Incorporating cardinality constraints
and synonym rules into conditional
functional dependencies . . . . . . . . 783--789
Satyajit Banerjee and
Atish Datta Chowdhury and
Subhas Kumar Ghosh Distributed approximation for maximum
weight matching on bounded degree
bounded integer weight graphs . . . . . 790--794
Fedor V. Fomin and
Petr A. Golovach and
Jan Kratochvíl and
Dieter Kratsch and
Mathieu Liedloff Sort and Search: Exact algorithms for
generalized domination . . . . . . . . . 795--798
Jean-Luc Baril More restrictive Gray codes for some
classes of pattern avoiding permutations 799--804
Weifan Wang and
Dong Chen $(2, 1)$-Total number of trees with
maximum degree three . . . . . . . . . . 805--810
Sizhong Zhou and
Qiqing Shen On fractional $(f, n)$-critical graphs 811--815
Dieter Rautenbach and
Friedrich Regen On packing shortest cycles in graphs . . 816--821
J. Wu and
R. Wei Comments on ``Distributed symmetric key
management for mobile ad hoc networks'' 822--824
Anonymous Editorial Board . . . . . . . . . . . . ??
Garth Isaak and
Robert Jamison and
Darren Narayan Greedy rankings and arank numbers . . . 825--827
Meirun Chen and
Jianguo Qian On $f$-fault tolerant arc-forwarding and
optical indices of all-optical folded
hypercubes . . . . . . . . . . . . . . . 828--831
Byungchun Chung and
Junbeom Hur and
Heeyoul Kim and
Seong-Min Hong and
Hyunsoo Yoon Improved batch exponentiation . . . . . 832--837
Jovan Dj. Goli\'c and
Guglielmo Morgari Optimal correlation attack on the
multiplexer generator . . . . . . . . . 838--841
Takaaki Mizuki and
Takuya Sato and
Hideaki Sone A one-round secure message broadcasting
protocol through a key sharing tree . . 842--845
Fangguo Zhang and
Xiaofeng Chen Cryptanalysis and improvement of an
ID-based ad-hoc anonymous identification
scheme at CT-RSA 05 . . . . . . . . . . 846--849
S\lawomir Lasota EXPSPACE lower bounds for the simulation
preorder between a communication-free
Petri net and a finite-state system . . 850--855
Erfang Shan and
Yanxia Dong and
Yukun Cheng The twin domination number in
generalized de Bruijn digraphs . . . . . 856--860
Markus Grassl and
Rainer Steinwandt Cryptanalysis of an authentication
scheme using truncated polynomials . . . 861--863
Amihood Amir and
Gonzalo Navarro Parameterized matching on non-linear
structures . . . . . . . . . . . . . . . 864--867
Okan Yilmaz and
Ing-Ray Chen Elastic threshold-based admission
control for QoS satisfaction with reward
optimization for servicing multiple
priority classes in wireless networks 868--875
Jian Li An $O(\log n / \log \log n)$ upper bound
on the price of stability for undirected
Shapley network design games . . . . . . 876--878
Elvira Albert and
John Gallagher and
Miguel Gómez-Zamalloa and
Germán Puebla Type-based homeomorphic embedding for
online termination . . . . . . . . . . . 879--886
Anonymous Editorial Board . . . . . . . . . . . . ??
J. García-Nieto and
E. Alba and
L. Jourdan and
E. Talbi Sensitivity and specificity based
multiobjective approach for feature
selection: Application to cancer
diagnosis . . . . . . . . . . . . . . . 887--896
Seung Geol Choi and
Javier Herranz and
Dennis Hofheinz and
Jung Yeon Hwang and
Eike Kiltz and
Dong Hoon Lee and
Moti Yung The Kurosawa--Desmedt key encapsulation
is not chosen-ciphertext secure . . . . 897--901
A. Moreno and
E. Cesar and
J. Sorribes and
T. Margalef and
E. Luque Task distribution using factoring load
balancing in Master--Worker applications 902--906
Chandan Saha and
Sandip Das Covering a set of points in a plane
using two parallel rectangles . . . . . 907--912
Kangbok Lee and
Byung-Cheon Choi and
Joseph Y.-T. Leung and
Michael L. Pinedo Approximation algorithms for multi-agent
scheduling to minimize total weighted
completion time . . . . . . . . . . . . 913--917
Sean Cleary and
Katherine St. John Rotation distance is fixed-parameter
tractable . . . . . . . . . . . . . . . 918--922
Sanjay Jain On some open problems in monotonic and
conservative learning . . . . . . . . . 923--926
Miklós Bóna and
Ryan Flynn The average number of block interchanges
needed to sort a permutation and a
recent result of Stanley . . . . . . . . 927--931
Sylwia Cichacz and
Dalibor Froncek Factorization of $K_{n, n}$ into $(0,
j)$-prisms . . . . . . . . . . . . . . . 932--934
Dror Aiger and
Klara Kedem Geometric pattern matching for point
sets in the plane under similarity
transformations . . . . . . . . . . . . 935--940
Wanwei Liu and
Ji Wang A tighter analysis of Piterman's Büchi
determinization . . . . . . . . . . . . 941--945
Gábor Erdélyi and
Lane A. Hemaspaandra and
Jörg Rothe and
Holger Spakowski Frequency of correctness versus average
polynomial time . . . . . . . . . . . . 946--949
Nicolas Bourgeois and
Bruno Escoffier and
Vangelis Th. Paschos Approximation of min coloring by
moderately exponential algorithms . . . 950--954
Marc Mörig and
Dieter Rautenbach and
Michiel Smid and
Jan Tusch An $\Omega(n \log n)$ lower bound for
computing the sum of even-ranked
elements . . . . . . . . . . . . . . . . 955--956
Marek Cygan and
\Lukasz Kowalik and
Mateusz Wykurz Exponential-time approximation of
weighted set cover . . . . . . . . . . . 957--961
Jussi Kujala Assembling approximately optimal binary
search trees efficiently using
arithmetics . . . . . . . . . . . . . . 962--966
GuanJun Liu and
ChangJun Jiang On conditions for the liveness of weakly
persistent nets . . . . . . . . . . . . 967--970
Peter Dankelmann and
Lutz Volkmann Minimum size of a graph or digraph of
given radius . . . . . . . . . . . . . . 971--973
Anonymous Editorial Board . . . . . . . . . . . . ??
Bang Ye Wu An optimal algorithm for the
maximum-density path in a tree . . . . . 975--979
Tomás Feder and
Heikki Mannila and
Evimaria Terzi Approximating the Minimum Chain
Completion problem . . . . . . . . . . . 980--985
Zsolt Gazdag and
Szabolcs Iván and
Judit Nagy-György Improved upper bounds on synchronizing
nondeterministic automata . . . . . . . 986--990
Kewen Zhao and
Yue Lin and
Ping Zhang A sufficient condition for pancyclic
graphs . . . . . . . . . . . . . . . . . 991--996
Xindong Zhang and
Juan Liu and
Jixiang Meng The bondage number in complete
$t$-partite digraphs . . . . . . . . . . 997--1000
Ian Wehrman and
C. A. R. Hoare and
Peter W. O'Hearn Graphical models of separation logic . . 1001--1004
Jialin Zhang and
Wei Chen Bounded cost algorithms for multivalued
consensus using binary consensus
instances . . . . . . . . . . . . . . . 1005--1009
Anthony Widjaja To Unary finite automata vs. arithmetic
progressions . . . . . . . . . . . . . . 1010--1014
Simona E. Rombo Optimal extraction of motif patterns in
$2$D . . . . . . . . . . . . . . . . . . 1015--1020
Anonymous Editorial Board . . . . . . . . . . . . ??
Woo Hyun Ahn and
Kyungjae Lee and
Jaewon Oh and
Kyungsub Min and
Joon Sung Hong A multiple-file write scheme for
improving write performance of small
files in Fast File System . . . . . . . 1021--1026
M. T. Juan and
J. J. Liu and
Y. L. Wang Errata for ``Faster index for property
matching'' . . . . . . . . . . . . . . . 1027--1029
Jakob Nordström A simplified way of proving trade-off
results for resolution . . . . . . . . . 1030--1035
Koki Hamada and
Kazuo Iwama and
Shuichi Miyazaki An improved approximation lower bound
for finding almost stable maximum
matchings . . . . . . . . . . . . . . . 1036--1040
B. S. Panda and
Sajal K. Das A parallel algorithm for generating
bicompatible elimination orderings of
proper interval graphs . . . . . . . . . 1041--1046
Mohammed Haddad and
Hamamache Kheddouci A strict strong coloring of trees . . . 1047--1054
Edgar G. Daylight and
Wouter M. Koolen and
Paul M. B. Vitányi Time-bounded incompressibility of
compressible strings and sequences . . . 1055--1059
Gautam K. Das and
Debapriyay Mukhopadhyay and
Subhas C. Nandy Improved algorithm for the widest empty
$1$-corner corridor . . . . . . . . . . 1060--1065
Joong Chae Na and
Dong Kyue Kim and
Jeong Seop Sim Finding the longest common
nonsuperstring in linear time . . . . . 1066--1070
Olaf Beyersdorff and
Arne Meier and
Michael Thomas and
Heribert Vollmer The complexity of propositional
implication . . . . . . . . . . . . . . 1071--1077
Sebastian Czerwi\'nski and
Jaros\law Grytczuk and
Wiktor \.Zelazny Lucky labelings of graphs . . . . . . . 1078--1081
Amr Elmasry Computing the subset partial order for
dense families of sets . . . . . . . . . 1082--1086
Jens Maßberg and
Dieter Rautenbach Binary trees with choosable edge lengths 1087--1092
Xianhui Lu and
Xuejia Lai and
Dake He Improved efficiency of Kiltz07-KEM . . . 1093--1096
Hai Liu and
Lizhuang Ma and
Xuan Cai and
Zhihua Chen and
Yang Shen A closed-form solution to video matting
of natural snow . . . . . . . . . . . . 1097--1104
Louis Ibarra A simple algorithm to find Hamiltonian
cycles in proper interval graphs . . . . 1105--1108
Anonymous Editorial Board . . . . . . . . . . . . ??
Chris Giannella New instability results for
high-dimensional nearest neighbor search 1109--1113
Zeev Nutov A note on Rooted Survivable Networks . . 1114--1119
Bin Ma and
Hongyi Yao Seed optimization for i.i.d.
similarities is no easier than optimal
Golomb ruler design . . . . . . . . . . 1120--1124
Jacob Jan Paulus and
Deshi Ye and
Guochuan Zhang Optimal online-list batch scheduling . . 1125--1128
Chia-Jui Lai A note on path bipancyclicity of
hypercubes . . . . . . . . . . . . . . . 1129--1130
Stanislav \vZivný Structural properties of oracle classes 1131--1135
Zeev Nutov and
Ariel Yaroshevitch Wireless network design via
$3$-decompositions . . . . . . . . . . . 1136--1140
Bernd Bank and
Marc Giusti and
Joos Heintz and
Luis Miguel Pardo On the intrinsic complexity of point
finding in real singular hypersurfaces 1141--1144
Daniel Andersson Hashiwokakero is NP-complete . . . . . . 1145--1146
Anonymous Editorial Board . . . . . . . . . . . . ??
Zuhua Shao Security of self-certified signatures 1147--1150
Yanmei Hong and
Zhao Zhang Vertex fault tolerance of
optimal-$\kappa$ graphs and
super-$\kappa$ graphs . . . . . . . . . 1151--1155
Alain Bretto and
Thierry Vallée A clique-covering sufficient condition
for Hamiltonicity of graphs . . . . . . 1156--1160
Dániel Marx and
Igor Razgon Constant ratio fixed-parameter
approximation of the edge multicut
problem . . . . . . . . . . . . . . . . 1161--1166
Steven Bitner and
Ovidiu Daescu Farthest segments and extremal triangles
spanned by points in $\mathbb{R}^3$ . . 1167--1171
Shlomi Dolev and
Yuval Elovici and
Rami Puzis and
Polina Zilberman Incremental deployment of network
monitors based on Group Betweenness
Centrality . . . . . . . . . . . . . . . 1172--1176
Chuan-Min Lee On the complexity of signed and minus
total domination in graphs . . . . . . . 1177--1181
Anonymous Editorial Board . . . . . . . . . . . . ??
Andre Raspaud and
Jiaojiao Wu Game chromatic number of toroidal grids 1183--1186
Min-Sheng Lin and
Yung-Jui Chen Counting the number of vertex covers in
a trapezoid graph . . . . . . . . . . . 1187--1192
Hervé Hocquard and
Mickaël Montassier Every planar graph without cycles of
lengths $4$ to $12$ is acyclically
$3$-choosable . . . . . . . . . . . . . 1193--1196
Zhan-jun Xue and
San-yang Liu An optimal result on fault-tolerant
cycle-embedding in alternating group
graphs . . . . . . . . . . . . . . . . . 1197--1201
Xing Chen and
Juan Liu and
Jixiang Meng The restricted arc connectivity of
Cartesian product digraphs . . . . . . . 1202--1205
Ming-Chien Yang Edge-fault-tolerant node-pancyclicity of
twisted cubes . . . . . . . . . . . . . 1206--1210
Ji Tian and
T. C. E. Cheng and
C. T. Ng and
Jinjiang Yuan Online scheduling on unbounded
parallel-batch machines to minimize the
makespan . . . . . . . . . . . . . . . . 1211--1215
Celina M. H. de Figueiredo and
Guilherme D. da Fonseca Enclosing weighted points with an
almost-unit ball . . . . . . . . . . . . 1216--1221
Anonymous Editorial Board . . . . . . . . . . . . ??
Olivier Finkel and
Dominique Lecomte Decision problems for Turing machines 1223--1226
Kristóf Bérczi and
Satoru Fujishige and
Naoyuki Kamiyama A linear-time algorithm to find a pair
of arc-disjoint spanning in-arborescence
and out-arborescence in a directed
acyclic graph . . . . . . . . . . . . . 1227--1231
David Eisenstat $k$-Fold unions of low-dimensional
concept classes . . . . . . . . . . . . 1232--1234
Frédéric Maffray Stable sets in $k$-colorable $P_5$-free
graphs . . . . . . . . . . . . . . . . . 1235--1237
Zexuan Ji and
Qiang Chen and
Quan-Sen Sun and
De-Shen Xia A moment-based nonlocal-means algorithm
for image denoising . . . . . . . . . . 1238--1244
R\uazvan Diaconescu An encoding of partial algebras as total
algebras . . . . . . . . . . . . . . . . 1245--1251
Guofeng Yan and
Jianxin Wang and
Weiping Wang An analytical model for end-to-end
communication channel over PLCN based on
QBDs . . . . . . . . . . . . . . . . . . 1252--1259
Woo Kwon Koo and
Jung Yeon Hwang and
Dong Hoon Lee Security vulnerability in a
non-interactive ID-based proxy
re-encryption scheme . . . . . . . . . . 1260--1262
Anonymous Editorial Board . . . . . . . . . . . . ??
Pavel Hrube\vs and
Amir Yehudayoff Monotone separations for constant degree
polynomials . . . . . . . . . . . . . . 1--3
Jorge Almeida and
Ond\vrej Klíma A counterexample to a conjecture
concerning concatenation hierarchies . . 4--7
Periklis A. Papakonstantinou A note on width-parameterized SAT: An
exact machine-model characterization . . 8--12
Jialin Zhang and
Wei Chen Implementing uniform reliable broadcast
with binary consensus in systems with
fair-lossy links . . . . . . . . . . . . 13--19
Lei Chen and
Changhong Lu and
Zhenbing Zeng A linear-time algorithm for
paired-domination problem in strongly
chordal graphs . . . . . . . . . . . . . 20--23
Kangbok Lee and
Joseph Y.-T. Leung and
Michael L. Pinedo A note on graph balancing problems with
restrictions . . . . . . . . . . . . . . 24--29
Roman \vCada and
Tomá\vs Kaiser and
Moshe Rosenfeld and
Zden\vek Ryjá\vcek Disjoint Hamilton cycles in the star
graph . . . . . . . . . . . . . . . . . 30--35
Fumiya Okubo A note on the descriptional complexity
of semi-conditional grammars . . . . . . 36--40
Anonymous Editorial Board . . . . . . . . . . . . ??
Sun-Yuan Hsieh and
Che-Nan Kuo and
Hsin-Hung Chou A further result on fault-free cycles in
faulty folded hypercubes . . . . . . . . 41--43
Lech Adamus and
Beata Orchel and
Artur Szyma\'nski and
A. Pawe\l Wojda and
Ma\lgorzata Zwonek A note on $t$-complementing permutations
for graphs . . . . . . . . . . . . . . . 44--45
Jyh-haw Yeh Enforcing non-hierarchical access
policies by hierarchical key assignment
schemes . . . . . . . . . . . . . . . . 46--49
Kung-Jui Pai and
Jou-Ming Chang and
Yue-Li Wang Upper bounds on the queuenumber of
$k$-ary $n$-cubes . . . . . . . . . . . 50--56
Ton van Deursen and
Sa\vsa Radomirovi\'c On a new formal proof model for RFID
location privacy . . . . . . . . . . . . 57--61
Mohamed Medhat Gaber and
Uwe Roehm and
Karel Herink An analytical study of central and
in-network data processing for wireless
sensor networks . . . . . . . . . . . . 62--70
Meijie Ma and
Baodong Liu Cycles embedding in exchanged hypercubes 71--76
Xie-Bin Chen Hamiltonian paths and cycles passing
through a prescribed path in hypercubes 77--82
Anonymous Editorial Board . . . . . . . . . . . . ??
Moonju Park Comments on ``Generalized rate monotonic
schedulability bounds using relative
period ratios'' . . . . . . . . . . . . 334--337
Andrzej Lingas and
Leonidas Palios and
Agnieszka Wasylewicz and
Pawel Zyli\'nski Corrigendum to ``Note on covering
monotone orthogonal polygons'' [Inf.
Process. Lett. \bf 104(6) (2007)
220--227] . . . . . . . . . . . . . . . 646--654