Last update: Fri Oct 20 15:25:20 MDT 2023
Volume 52, Number 4, November 25, 1994Rajesh 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