Last update:
Fri Jul 4 09:24:19 MDT 2008
Greg N. Frederickson Scheduling Unit-Time Tasks with Integer
Release Times and Deadlines . . . . . . 171--173
J. Pierre Verjus On the proof of a distributed algorithm 145--147
Kurt Mehlhorn A faster approximation algorithm for the
Steiner problem in graphs . . . . . . . 125--128
Kerry Raymond A distributed algorithm for multiple
entries to a critical section . . . . . 189--193
Martin Kochol Efficient monotone circuits for
threshold functions . . . . . . . . . . 121--122
Erkki Mäkinen On the subtree isomorphism problem for
ordered trees . . . . . . . . . . . . . 271--273
P. Crescenzi and
R. Silvestri Relative complexity of evaluating the
optimum cost and constructing the
optimum for maximization problems . . . 221--226
Hitoshi Suzuki and
Naomi Takahashi and
Takao Nishizeki A linear algorithm for bipartition of
biconnected graphs . . . . . . . . . . . 227--231
Yijie Han and
Yoshihide Igarashi Time lower bounds for sorting on
multi-dimensional mesh-connected
processor arrays . . . . . . . . . . . . 233--238
Jürgen Kämper A result relating disjunctive
self-reducibility to $P$-immunity . . . 239--242
C. S. Kannan and
Henry Y. H. Chuang Fast Hough transform on a mesh connected
processor array . . . . . . . . . . . . 243--248
Laurence Boxer and
Russ Miller Common intersections of polygons . . . . 249--254
Divyakant Agrawal and
Amr El Abbadi Exploiting logical structures in
replicated databases . . . . . . . . . . 255--260
Victor Shoup On the deterministic complexity of
factoring polynomials over finite fields 261--267
Richard J. Anderson and
Gary L. Miller A simple randomized parallel algorithm
for list-ranking . . . . . . . . . . . . 269--273
Alan A. Bertossi and
Sabrina Moretti Parallel algorithms on circular-arc
graphs . . . . . . . . . . . . . . . . . 275--281
Michael B. Dillencourt Realizability of Delaunay triangulations 283--287
Neil J. Gunther and
John G. Shaw Path integral evaluation of ALOHA
network transients . . . . . . . . . . . 289--295
Tom Altman and
Bogdan S. Chlebus Sorting roughly sorted sequences in
parallel . . . . . . . . . . . . . . . . 297--300
Stephan Olariu A generalization of Chvatal's
star-cutset lemma . . . . . . . . . . . 301--303
Torben Hagerup and
Christine Rüb A guided tour of Chernoff bounds . . . . 305--308
Zvi Galil and
Kunsoo Park A linear-time algorithm for concave
one-dimensional dynamic programming . . 309--311
Philips Hingston and
Ross Wilkinson A distributed join algorithm . . . . . . 313--317
Samir Khuller and
Joseph S. B. Mitchell On a triangle counting problem . . . . . 319--321
Edgar Knapp A predicate transformer for progress . . 323--330
Masahito Kurihara and
Ikuo Kaji Modular term rewriting systems and the
termination . . . . . . . . . . . . . . 1--4
Mohan Ahuja Flush primitives for asynchronous
distributed systems . . . . . . . . . . 5--12
Shai Simonson Routing with critical paths . . . . . . 13--19
Arne Andersson and
Svante Carlsson Construction of a tree from its
traversals in optimal time and space . . 21--25
Jeremy Jacob Separability and the detection of hidden
channels . . . . . . . . . . . . . . . . 27--29
Alejandro D. Martinez and
Rosita Wachenchauzer and
Rafael D. Lins Cyclic reference counting with local
mark-scan . . . . . . . . . . . . . . . 31--35
O. J. Murphy and
S. M. Selkow Finding nearest neighbors with Voronoi
tessellations . . . . . . . . . . . . . 37--41
Carla Neaderhouser Purdy and
George B. Purdy The area-time complexity of the greatest
common divisor problem: a lower bound 43--46
Joseph Y.-T. Leung and
Gilbert H. Young Preemptive scheduling to minimize mean
weighted flow time . . . . . . . . . . . 47--50
R. Morrison and
M. P. Atkinson and
A. L. Brown and
A. Dearle On the classification of binding
mechanisms . . . . . . . . . . . . . . . 51--55
Simeon Ntafos The robber route problem . . . . . . . . 59--63
Pradip Dey and
Barrett R. Bryant and
Tadao Takaoka Lexical ambiguity in tree adjoining
grammars . . . . . . . . . . . . . . . . 65--69
Young C. Wee and
Seth Chaiken and
Dan E. Willard On the angle restricted nearest neighbor
problem . . . . . . . . . . . . . . . . 71--76
Sandeep Sen Finding an approximate median with high
probability in constant parallel time 77--80
Stephen Cook and
Toniann Pitassi A feasibly constructive lower bound for
resolution proofs . . . . . . . . . . . 81--85
Jean-Paul Laumond Connectivity of plane triangulations . . 87--96
Stephan Olariu On the closure of triangle-free graphs
under substitution . . . . . . . . . . . 97--101
Michel Cosnard and
Jean Duprat and
Afonso G. Ferreira The complexity of searching in X+Y and
other multisets . . . . . . . . . . . . 103--109
C. A. R. Hoare Fixed points of increasing functions . . 111--112
J. M. Pallo A distance metric on binary trees using
lattice-theoretic measures . . . . . . . 113--116
A. Bertoni and
M. Goldwurm and
P. Massazza Counting problems and algebraic formal
power series in noncommuting variables 117--121
Lein Harn and
Thomas Kiesler An efficient probabilistic encryption
scheme . . . . . . . . . . . . . . . . . 123--129
Moon Hwa Park and
Myunghwan Kim A distributed synchronization scheme for
fair multi-process handshakes . . . . . 131--138
Henk Goeman Towards a theory of (self) applicative
communicating processes. A short note 139--142
Christoph Meinel Logic vs. complexity theoretic
properties of the graph accessibility
problem for directed graphs of bounded
degree . . . . . . . . . . . . . . . . . 143--146
Shang-Hua Teng Space efficient Processor Identity
protocol . . . . . . . . . . . . . . . . 147--154
John C. Tipper A straightforward iterative algorithm
for the planar Voronoi diagram . . . . . 155--160
Jürgen Plehn Preemptive scheduling of independent
jobs with release times and deadlines on
a hypercube . . . . . . . . . . . . . . 161--166
Udi Manber Recognizing breadth-first search trees
in linear time . . . . . . . . . . . . . 167--171
L. V. Kale An almost perfect heuristic for the
$N$-nonattacking queens problem . . . . 173--178
Earlin Lutz Some proofs of data refinement . . . . . 179--185
Biing-Feng Wang and
Gen-Huey Chen and
Ferng-Ching Lin Constant time sorting on a processor
array with a reconfigurable bus system 187--192
James H. Bradford Sequence matching with binary codes . . 193--196
A. Bagchi and
S. L. Hakimi and
J. Mitchem and
E. Schmeichel Parallel algorithms for gossiping by
mail . . . . . . . . . . . . . . . . . . 197--202
Samir Khuller Coloring algorithms for K$_5$-minor free
graphs . . . . . . . . . . . . . . . . . 203--208
James Cooper and
Leslie Kitchen CASOP: A fast algorithm for computing
the $n$-ary composition of a binary
associative operator . . . . . . . . . . 209--213
G. Ramalingam and
C. Pandu Rangan New sequential and parallel algorithms
for interval graph recognition . . . . . 215--219
P. E. Dunne Comment on Kochol's paper ``Efficient
monotone circuits for threshold
functions'' [Inform. Process. Lett. \bf
32(3), 24 August 1989, pp. 121--122] . . 221--222
Stefan Ronn and
Heikki Saikkonen Distributed termination detection with
counters . . . . . . . . . . . . . . . . 223--227
Zsolt Tuza Periodic string division generated by
deterministic $L$ systems . . . . . . . 229--234
Sung Kwon Kim A parallel algorithm for finding a
maximum clique of a set of circular arcs
of a circle . . . . . . . . . . . . . . 235--241
Owen Murphy A unifying framework for trie design
heuristics . . . . . . . . . . . . . . . 243--249
William Pugh Slow optimally balanced search
strategies vs. cached fast uniformly
balanced search strategies . . . . . . . 251--254
A. Pombortsis Sharing special purpose resources in a
multiprocessor environment . . . . . . . 255--260
R. T. Kuo and
S. S. Tseng The necessary and sufficient condition
for the worst-case male optimal stable
matching . . . . . . . . . . . . . . . . 261--263
J. M. Robson Random access machines with
multi-dimensional memories . . . . . . . 265--266
Mark Allen Weiss and
Robert Sedgewick More on Shellsort increment sequences 267--270
Gaston H. Gonnet and
Ricardo A. Baeza-Yates An analysis of the Karp-Rabin string
matching algorithm . . . . . . . . . . . 271--274
Ingo Althöfer Tight lower bounds on the length of word
chains . . . . . . . . . . . . . . . . . 275--276
Oded Goldreich A note on computational
indistinguishability . . . . . . . . . . 277--281
N. Chandrasekharan Isomorphism testing of $k$-trees is in
NC, for fixed $k$ . . . . . . . . . . . 283--287
Jan Chomicki and
V. S. Subrahmanian Generalized closed world assumption is
$\Pi_2^0$-complete . . . . . . . . . . . 289--291
Lenwood S. Heath Covering a set with arithmetic
progressions is NP-complete . . . . . . 293--298
M. R. Zargham and
K. J. Danhof Toward a definition of fault analysis
for Petri nets models . . . . . . . . . 299--305
Philip Klein and
Clifford Stein A parallel algorithm for eliminating
cycles in undirected graphs . . . . . . 307--312
Gabriel Matsliach and
Oded Shmueli Distributing a $B^+$-tree in a loosely
coupled environment . . . . . . . . . . 313--321
A. Sengupta and
S. Bandyopadhyay Deadlock-free routing in $k$-ary
hypercube network in presence of
processor failures . . . . . . . . . . . 323--328
Mitchell Wand A short proof of the lexical addressing
algorithm . . . . . . . . . . . . . . . 1--5
Mohan Ahuja and
Yahui Zhu An $O(n\log n)$ feasibility algorithm
for preemptive scheduling of $n$
independent jobs on a hypercube . . . . 7--11
Alok Aggarwal and
Subhash Suri Computing the longest diagonal of a
simple polygon . . . . . . . . . . . . . 13--18
Jeremy Jacob A model of reconfiguration in
communicating sequential processes . . . 19--22
Chanderjit L. Bajaj and
Tamal Dey Polygon nesting and robustness . . . . . 23--32
Rani Siromoney and
Lisa Mathew A public key cryptosystem based on
Lyndon words . . . . . . . . . . . . . . 33--36
Yu-Tai Ching and
Kurt Mehlhorn and
Michiel H. M. Smid Dynamic deferred data structuring . . . 37--40
E. Lodi and
F. Luccio and
L. Pagli Routing in times square mode . . . . . . 41--48
Ronitt Rubinfeld The cover time of a regular expander is
$O(n\log n)$ . . . . . . . . . . . . . . 49--51
L. Boxer and
R. Miller Corrigenda: ``Common intersections of
polygons'' [Inform. Process. Lett. \bf
33(5), 10 January 1990, pp. 249--254] 53--53
D. Kumar and
S. S. Iyengar and
M. B. Sharma Corrections to a distributed depth-first
search algorithm . . . . . . . . . . . . 55--56
Anna Lubiw Counterexample to a conjecture of
Szymanski on hypercube routing . . . . . 57--61
Ted Herman Probabilistic self-stabilization . . . . 63--67
G. R. Guenther Efficient expansion of factored
expressions . . . . . . . . . . . . . . 69--72
Maurice Maes On a cyclic string-to-string correction
problem . . . . . . . . . . . . . . . . 73--78
D. T. Barnard and
D. B. Skillicorn Pipelining tree-structured algorithms on
SIMD architectures . . . . . . . . . . . 79--84
Khun Yee Fung and
Tina M. Nicholl and
Robert E. Tarjan and
Christopher J. Van Wyk Simplified linear-time Jordan sorting
and polygon clipping . . . . . . . . . . 85--92
Ching-Lin Wang Obtaining lazy evaluation with
continuations in Scheme . . . . . . . . 93--97
Ingo Wegener Efficient simulation of circuits by EREW
PRAMs . . . . . . . . . . . . . . . . . 99--102
Martha Sideris On attribute grammars without attribute
synthesis . . . . . . . . . . . . . . . 103--109
Tom Altman and
George Logothetis A note on ambiguity in context-free
grammars . . . . . . . . . . . . . . . . 111--114
Erik Lambrichts and
Peter Nees and
Jan Paredaens and
Peter Peelman and
Letizia Tanca Checking functional consistency in
deductive databases . . . . . . . . . . 115--120
Maxime Crochemore and
Wojciech Rytter Parallel construction of minimal suffix
and factor automata . . . . . . . . . . 121--128
Marta Z. Kwiatkowska A metric for traces . . . . . . . . . . 129--135
K. Mehlhorn and
S. Näher and
C. Uhrig Hidden line elimination for isooriented
rectangles . . . . . . . . . . . . . . . 137--143
Moshe Y. Vardi Endmarkers can make a difference . . . . 145--148
Srinivasa Rao Arikati and
C. Pandu Rangan Linear algorithm for optimal path cover
problem on interval graphs . . . . . . . 149--153
John Launchbury Strictness analysis aids inductive
proofs . . . . . . . . . . . . . . . . . 155--159
Jerzy A. Piotrowski A functional model of a simplified
sequential machine . . . . . . . . . . . 161--166
Chau-Jy Lin Parallel algorithm for generating
permutations on linear array . . . . . . 167--170
Mohamed G. Gouda and
Ted Herman Stabilizing unison . . . . . . . . . . . 171--175
Shyan-Ming Yuan The communication complexity for
decentralized evaluation of functions 177--182
Kurt Mehlhorn and
Stefan Näher Bounded ordered dictionaries in $O(\log
\log n)$ time and $O(n)$ space . . . . . 183--189
P. Inverardi and
M. Nesi A rewriting strategy to verify
observational congruence . . . . . . . . 191--199
Noga Alon Generating pseudo-random permutations
and maximum flow algorithms . . . . . . 201--204
Glenn K. Manacher and
Terrance A. Mankus and
Carol Joan Smith An optimum $\Theta (n \log n)$ algorithm
for finding a canonical Hamiltonian path
and a canonical Hamiltonian circuit in a
set of intervals . . . . . . . . . . . . 205--211
Xiaotie Deng An optimal parallel algorithm for linear
programming in the plane . . . . . . . . 213--217
Kenneth Block and
Tai-Kuo Woo A more efficient generalization of
Peterson's mutual exclusion algorithm 219--222
Michael C. Loui and
Milind A. Sohoni An algorithm for load balancing in
multiprocessor systems . . . . . . . . . 223--228
Seinosuke Toda On the complexity of topological sorting 229--233
Erich Grädel Simple interpretations among complicated
theories . . . . . . . . . . . . . . . . 235--238
Ken Grigg and
Serge Miguet and
Yves Robert Symmetric matrix-vector product on a
ring of processors . . . . . . . . . . . 239--248
Robert J. Cimikowski Finding Hamiltonian cycles in certain
planar graphs . . . . . . . . . . . . . 249--254
Maw Shang Chang and
Nen-Fu Huang and
Chuan-Yi Tang An optimal algorithm for constructing
oriented Voronoi diagrams and geographic
neighborhood graphs . . . . . . . . . . 255--260
Lisa Hellerstein and
Philip Klein and
Robert Wilber On the time-space complexity of
reachability queries for preprocessed
graphs . . . . . . . . . . . . . . . . . 261--267
Matthew T. Dickerson and
R. Scot Drysdale Fixed-radius near neighbors search
algorithms for points and segments . . . 269--273
A. J. M. Van Gasteren and
G. Tel Comments on ``On the proof of a
distributed algorithm'': always-true is
not invariant . . . . . . . . . . . . . 277--279
David B. Shmoys and
David P. Williamson Analyzing the Held-Karp TSP bound. A
monotonicity property with application 281--285
A. W. Mostowski Alternating automata with start formulas 287--290
George Karner A note on terminal balancing of
algebraic systems . . . . . . . . . . . 291--293
Chain-Chin Yen and
R. C. T. Lee The weighted perfect domination problem 295--299
Alok Aggarwal and
Tom Leighton A tight lower bound for the train
reversal problem . . . . . . . . . . . . 301--304
Chwan-Hwa Wu and
Chia-Jiu Wang and
Heng-Ming Tai Application of exponential
hetero-associative memory on frequency
classifier . . . . . . . . . . . . . . . 305--311
Jang-Ping Sheu and
Jyh-Shyan Tang Efficient parallel $k$ selection
algorithm . . . . . . . . . . . . . . . 313--316
Sun Wu and
Udi Manber and
Gene Myers and
Webb Miller $O(NP)$ sequence comparison algorithm 317--323
Andrew Chin On the depth complexity of the counting
functions . . . . . . . . . . . . . . . 325--328
Zhen Liu A Note on Graham's Bound . . . . . . . . 1--5
Wen-Huei Chen and
Ching-Sung Lu and
Elben R. Brozovsky and
Jin-Tuu Wang An optimization technique for protocol
conformance testing using multiple UIO
sequences . . . . . . . . . . . . . . . 7--11
Joanna J\polhkedrzejowicz Infinite hierarchy of shuffle
expressions over a finite alphabet . . . 13--17
Haklin Kim Finding a maximum independent set in a
permutation graph . . . . . . . . . . . 19--23
Frank Dederichs and
Rainer Weber Safety and liveness from a
methodological point of view . . . . . . 25--30
Biing-Feng Wang and
Gen-Huey Chen Two-Dimensional processor array with a
reconfigurable bus system is at least as
powerful as CRCW model . . . . . . . . . 31--36
Stanley Burris and
John Lawrence Unification in commutative rings is not
finitary . . . . . . . . . . . . . . . . 37--38
Malcolm C. Fields and
Greg N. Frederickson A faster algorithm for the maximum
weighted tardiness problem . . . . . . . 39--44
Oded Goldreich and
Erez Petrank The best of both worlds: guaranteeing
termination in fast randomized Byzantine
Agreement protocols . . . . . . . . . . 45--49
Ke Qiu and
Henk Meijer A note on diameter of acyclic directed
hypercubes . . . . . . . . . . . . . . . 51--52
Hans L. Bodlaender and
Gerard Tel Bit-optimal election in synchronous
rings . . . . . . . . . . . . . . . . . 53--56
Torben Hagerup and
Hong Shen Improved nonconservative sequential and
parallel integer sorting . . . . . . . . 57--63
Miklos Biro Object-oriented interaction in resource
constrained scheduling . . . . . . . . . 65--67
Anna Slobodova One-way globally deterministic
synchronized alternating finite automata
recognize exactly deterministic
context-sensitive languages . . . . . . 69--72
Stephen A. Vavasis Quadratic programming is in NP . . . . . 73--77
Jin-yi Cai Lower bounds for constant-depth circuits
in the presence of help bits . . . . . . 79--83
Jae Moon Lee and
Jong Soo Park and
Myunghwan Kim An upper bound on buffer size for join
operation using nonclustered indexes . . 85--90
Richard J. Lipton and
Arvin Park The processor identity problem . . . . . 91--94
Chandan Haldar and
L. M. Patnaik Oracle complexities for computational
geometry of semi-algebraic sets and
Voronoi diagrams . . . . . . . . . . . . 95--102
G. M. Megson and
F. M. F. Gaston Improved matrix triangularisation using
a double pipeline systolic array . . . . 103--109
De-Lei Lee Efficient address generation in a
parallel processor . . . . . . . . . . . 111--116
Jingde Cheng An algebraic semantics of notional
entailment logic Cn . . . . . . . . . . 117--121
Aphrodite Tsalgatidou Modelling and animating information
systems dynamics . . . . . . . . . . . . 123--127
Shuo-Yen Robert Li On full utilization of multi-channel
capacity with priority protocol . . . . 129--133
Laura A. Sanchis On the complexity of test case
generation for NP-hard problems . . . . 135--140
John G. Kollias and
Yannis Manolopoulos and
Christos H. Papadimitriou The optimum execution order of queries
in linear storage . . . . . . . . . . . 141--145
Lawrence L. Larmore An optimal algorithm with unknown time
complexity for convex matrix searching 147--151
R. Lin and
S. Olariu A fast parallel algorithm to recognize
partitionable graphs . . . . . . . . . . 153--157
A. Paulik Worst-case analysis of a generalized
heapsort algorithm . . . . . . . . . . . 159--165
Kim-Heng Teo and
Tai-Ching Tuan Performance analysis of greedy heuristic
to find a minimum total-jogs layout for
river routing . . . . . . . . . . . . . 167--170
Valmir C. Barbosa Blocking versus nonblocking interprocess
communication. A note on the effect on
concurrency . . . . . . . . . . . . . . 171--175
Hans Kleine Büning Existence of simple propositional
formulas . . . . . . . . . . . . . . . . 177--182
Xiaolei Qian An Axiom System for Database
Transactions . . . . . . . . . . . . . . 183--189
Gerhard Woeginger A simple solution to the two paths
problem in planar graphs . . . . . . . . 191--192
Edsger W. Dijkstra Making a fair roulette from a possibly
biased coin . . . . . . . . . . . . . . 193--193
S. Ramesh On the completeness of modular proof
systems . . . . . . . . . . . . . . . . 195--201
Erkki Makinen The grammatical inference problem for
the Szilard languages of linear grammars 203--206
Bernd-Jürgen Falkowski Perceptrons revisited . . . . . . . . . 207--213
Miros\law Kuty\lowski Remarks on sorting and one-way multihead
finite automata . . . . . . . . . . . . 215--218
Jozef Vyskoc Making bubblesort recursive . . . . . . 219--220
Hyoung Joong Kim and
Jang Gyu Lee Partial sum problem mapping into a
hypercube . . . . . . . . . . . . . . . 221--224
Jin Ho Hur and
Kilnam Chon Self and selftype . . . . . . . . . . . 225--230
Peter Damaschke and
Haiko Müller and
Dieter Kratsch Domination in convex and chordal
bipartite graphs . . . . . . . . . . . . 231--236
Ursula Martin A note on division orderings on strings 237--240
Jang-Ping Sheu and
Zen-Fu Chiang Efficient allocation of chain-like task
on chain-like network computers . . . . 241--245
Carsten Damm Problems complete for $\oplus L$ . . . . 247--250
Siu Wing Cheng and
Ravi Janardan Efficient dynamic algorithms for some
geometric intersection problems . . . . 251--258
Marc Gyssens and
Jan Paredaens and
Dirk Van Gucht On a hierarchy of classes for nested
databases . . . . . . . . . . . . . . . 259--266
O. M. Makarov On the synthesis of fast algorithms for
signal processing . . . . . . . . . . . 267--272
P. Dublish Some comments on the subtree isomorphism
problem for ordered trees . . . . . . . 273--275
Subir Kumar Ghosh and
Anil Maheshwari An optimal algorithm for computing a
minimum nested nonconvex polygon . . . . 277--280
F. Kocsis and
J. F. Böhme Rotation-based computations for
ray-tracing second-order surfaces and
curves . . . . . . . . . . . . . . . . . 281--283
Antonio Brogi and
Evelina Lamma and
Paola Mello Hypothetical reasoning in logic
programming. A semantic approach . . . . 285--291
Z. Fülöp and
S. Vágvölgyi The emptiness problem is undecidable for
domains of partial monadic $2$-modular
tree transformations . . . . . . . . . . 293--296
Rob R. Hoogerwoord A calculational derivation of the CASOP
algorithm . . . . . . . . . . . . . . . 297--299
Gabriel Matsliach Performance analysis of file
organizations that use multi-bucket data
leaves . . . . . . . . . . . . . . . . . 301--310
Kai Salomaa and
Sheng Yu The immortality problem for Lag systems 311--315
Giuseppe Di Battista and
Wei-Ping Liu and
Ivan Rival Bipartite graphs, upward drawings, and
planarity . . . . . . . . . . . . . . . 317--322
Sung Kwon Kim Parallel algorithms for the segment
dragging problem . . . . . . . . . . . . 323--327
Chung-Kuo Chang and
M. G. Gouda On the minimum requirements for
independent recovery in distributed
systems . . . . . . . . . . . . . . . . 1--7
Xubo Zhang Overlap closures do not suffice for
termination of general term rewriting
systems . . . . . . . . . . . . . . . . 9--11
Soma Chaudhuri and
Richard E. Ladner Safety and liveness of
$\omega$-context-free languages . . . . 13--20
Stephan Olariu An optimal greedy heuristic to color
interval graphs . . . . . . . . . . . . 21--25
Viggo Kann Maximum bounded $3$-dimensional matching
is MAX SNP-complete . . . . . . . . . . 27--35
Yannis Manolopoulos and
Athina Vakali Seek distances in disks with two
independent heads per surface . . . . . 37--42
U. K. Sarkar and
P. P. Chakrabarti and
S. Ghose and
S. C. De Sarkar Multiple stack branch and bound . . . . 43--48
Douglas Campbell and
John Higgins Minimal visibility graphs . . . . . . . 49--53
Bin Yu and
Xinggang Lin and
Youshou Wu The tree representation of the graph
used in binary image processing . . . . 55--59
Igor Litovsky Prefix-free languages as
$\omega$-generators . . . . . . . . . . 61--65
Fabrizio Luccio and
Andrea Pietracaprina and
Geppino Pucci Analysis of Parallel Uniform Hashing . . 67--69
Timothy Law Snyder Lower bounds for rectilinear Steiner
trees in bounded space . . . . . . . . . 71--74
C. C. Handley A space efficient distributive sort . . 75--78
Roberto Tamassia An incremental reconstruction method for
dynamic planar point location . . . . . 79--83
Yoshihiro Tanaka A dual algorithm for the satisfiability
problem . . . . . . . . . . . . . . . . 85--89
Richard Beigel and
Lane A. Hemachandra and
Gerd Wechsung Probabilistic polynomial time is closed
under parity reductions . . . . . . . . 91--94
J. von Wright Program inversion in the refinement
calculus . . . . . . . . . . . . . . . . 95--100
Alan Gibbons and
Ridha Ziani The balanced binary tree technique on
mesh-connected computers . . . . . . . . 101--109
Xin He An efficient parallel algorithm for
finding minimum weight matching for
points on a convex polygon . . . . . . . 111--116
Svante Carlsson An optimal algorithm for deleting the
root of a heap . . . . . . . . . . . . . 117--120
Sven Skyum A simple algorithm for computing the
smallest enclosing circle . . . . . . . 121--125
Jurek Czyzowicz and
K. B. Lakshmanan and
Andrzej Pelc Searching with a forbidden lie pattern
in responses . . . . . . . . . . . . . . 127--132
Udi Manber and
Ricardo Baeza-Yates An algorithm for string matching with a
sequence of don't cares . . . . . . . . 133--136
Pavol Duris and
Imrich Vrto Semelectivity is not sufficient . . . . 137--141
Bin Jiang Traversing graphs in a paging
environment, BFS or DFS? . . . . . . . . 143--147
Frederic Green Oracle separating $\oplus P$ from
$PP^{PH}$ . . . . . . . . . . . . . . . 149--153
A. J. E. M. Janssen An optimization problem related to
neural networks . . . . . . . . . . . . 155--157
Galen Sasaki The Effect of the Density of States on
the Metropolis Algorithm . . . . . . . . 159--163
D\~ung T. H\`uynh The effective entropies of some
extensions of context-free languages . . 165--169
Wladyslaw M. Turski On starvation and some related issues 171--174
Micha Hofri and
Hadas Shachnai On the optimality of the counter scheme
for dynamic linear lists . . . . . . . . 175--179\$
Zhaofang Wen Parallel multiple search . . . . . . . . 181--186
D. P. Jacobs Probabilistic checking of associativity
in algebras . . . . . . . . . . . . . . 187--191
Xiaotie Deng and
Sanjeev Mahajan Server problems and resistive spaces . . 193--196
Robert W. Irving On approximating the minimum independent
dominating set . . . . . . . . . . . . . 197--200
Xue-Hou Tan and
Tomio Hirata and
Yasuyoshi Inagaki The intersection searching problem for
$c$-oriented polygons . . . . . . . . . 201--204
C. Huizing and
W. P. de Roever Introduction to design choices in the
semantics of Statecharts . . . . . . . . 205--213
U. Zwick An extension of Khrapchenko's theorem 215--217
Y. Liang and
C. Rhee and
S. K. Dhall and
S. Lakshmivarahan A new approach for the domination
problem on permutation graphs . . . . . 219--224
Peter F. Corbett and
Isaac D. Scherson A unified algorithm for sorting on
multidimensional mesh-connected
processors . . . . . . . . . . . . . . . 225--231
Maria Serna Approximating linear programming is
log-space complete for P . . . . . . . . 233--236
H. Alt and
N. Blum and
K. Mehlhorn and
M. Paul Computing a maximum cardinality matching
in a bipartite graph in time
$O(n^{1.5}\sqrt m/log n)$ . . . . . . . 237--240
Shyan Ming Yuan Topological properties of supercube . . 241--245
James K. Mullin A Caution on Universal Classes of Hash
Functions . . . . . . . . . . . . . . . 247--256
Dani\`ele Beauquier An undecidable problem about rational
sets and contour words of polyominoes 257--263
Anne Kaldewaij and
Berry Schoenmakers The derivation of a tighter bound for
top-down skew heaps . . . . . . . . . . 265--271
Toshiya Itoh Characterization for a family of
infinitely many irreducible equally
spaced polynomials . . . . . . . . . . . 273--277
Yasubumi Sakakibara On learning from queries and
counterexamples in the presence of noise 279--284
Gadi Taubenfeld On the nonexistence of resilient
consensus protocols . . . . . . . . . . 285--289
Qingzhou Wang and
Kam Hoi Cheng List scheduling of parallel tasks . . . 291--297
Dirk Taubner A note on the notation of recursion in
process algebras . . . . . . . . . . . . 299--303
Kim-Heng Teo and
Tai-Ching Tuan An improved upper bound on the number of
intersections between two rectangular
paths . . . . . . . . . . . . . . . . . 305--309
Sabri A. Mahmoud Motion estimation based on modified
Fourier spectrum . . . . . . . . . . . . 311--313
Olivier Danvy Semantics-directed compilation of
nonlinear patterns . . . . . . . . . . . 315--322
K. Vidyasankar A very simple construction of $1$-writer
multireader multivalued atomic variable 323--326
Biing-Feng Wang and
Chuen-Liang Chen and
Gen-Huey Chen A simple approach to implementing
multiplication with small tables . . . . 327--329
Zvi Galil and
Giuseppe F. Italiano A note on set union with arbitrary
deunions . . . . . . . . . . . . . . . . 331--335
Myung-Joon Lee and
Kwang-Moo Choe ${\rm SLR}(k)$ covering for ${\rm
LR}(k)$ grammars . . . . . . . . . . . . 337--347
R. Srikant and
Kamala Krithivasan Fastest path across constrained moving
rectilinear obstacles . . . . . . . . . 349--353
Nageswara S. V. Rao and
Weixiong Zhang Building heaps in parallel . . . . . . . 355--358
Victor J. Dielissen and
Anne Kaldewaij Rectangular partition is polynomial in
two dimensions but NP-complete in three 1--6
P. Goral\vcík and
A. Goral\vcíková and
V. Koubek Alternation with a pebble . . . . . . . 7--13
Ivan Stojmenovi\'c Bisections and ham-sandwich cuts of
convex polygons and polyhedra . . . . . 15--21
Ahmed K. Elmagarmid and
Wei Min Du Integrity aspects of quasi
serializability . . . . . . . . . . . . 23--28
Shi-Jinn Horng and
Wen-Tsuen Chen and
Ming-Yi Fang Optimal speed-up algorithms for template
matching on SIMD hypercube
multiprocessors with restricted local
memory . . . . . . . . . . . . . . . . . 29--37
Victor Shoup Smoothness and factoring polynomials
over finite fields . . . . . . . . . . . 39--42
Xu Cheng A graph transformation algorithm for
concurrency control in a partitioned
database . . . . . . . . . . . . . . . . 43--48
Calvin C.-Y. Chen and
Sajal K. Das and
Selim G. Akl A unified approach to parallel
depth-first traversals of general trees 49--55
Maxime Crochemore and
Wojciech Rytter Efficient parallel algorithms to test
square-freeness and factorize strings 57--60
C. \`Alvarez and
J. Gabarró The parallel complexity of two problems
on concurrency . . . . . . . . . . . . . 61--70
Hsu Chun Yen A polynomial time algorithm to decide
pairwise concurrency of transitions for
$1$-bounded conflict-free Petri nets . . 71--76
Giovanni Manzini Radix sort on the hypercube . . . . . . 77--81
João Meidânis Lower bounds for arithmetic problems . . 83--87
Xavier Messeguer Dynamic behaviour in updating process
over BST of size two with probabilistic
deletion algorithms . . . . . . . . . . 89--100
Jayadev Misra Phase synchronization . . . . . . . . . 101--105
Steven Minsker The Towers of Antwerpen problem . . . . 107--111
Ming-Yang Kao and
Stephen R. Tate Online matching with blocked input . . . 113--116
David Fernández-Baca and
Mark A. Williams On matroids and hierarchical graphs . . 117--121
Günter Rote Computing the minimum Hausdorff distance
between two-point sets on a line under
translation . . . . . . . . . . . . . . 123--127
Lars Langemyr Circuits for computing the GCD of two
polynomials over an algebraic number
field . . . . . . . . . . . . . . . . . 129--134
Charles Martel Self-adjusting multi-way search trees 135--141
Subbiah Rajanarayanan and
Sitharama S. Iyengar A new optimal distributed algorithm for
the set intersection problem . . . . . . 143--148
Günter Rote and
Gerhard Woeginger and
Binhai Zhu and
Zhengyan Wang Counting $k$-subsets and convex $k$-gons
in the plane . . . . . . . . . . . . . . 149--151
Michal Mnuk A div($n$) depth Boolean circuit for
smooth modular inverse . . . . . . . . . 153--156
P. Pramanik and
P. K. Das and
A. K. Bandyopadhyay and
D. Q. M. Fay A deadlock-free communication kernel for
loop architecture . . . . . . . . . . . 157--161
Dragan M. Acketa and
Jovi\vsa D. \vZuni\'c On the number of linear partitions of
the $(m,n)$-grid . . . . . . . . . . . . 163--168
James H. Bradford and
T. A. Jenkyns On the inadequacy of tournament
algorithms for the $N$-SCS problem . . . 169--171
Marek Chrobak and
Lawrence L. Larmore A note on the server problem and a
benevolent adversary . . . . . . . . . . 173--175
Rolf Floren A note on: ``A faster approximation
algorithm for the Steiner problem in
graphs'' [Inform. Process. Lett. \bf 27
(1988), no. 3, 125--128; MR 89d:68031]
by K. Mehlhorn . . . . . . . . . . . . . 177--178
Andrew V. Goldberg Processor-efficient implementation of a
maximum flow algorithm . . . . . . . . . 179--185
Laurent Siklossy and
Eduard Tulp The space reduction method: a method to
reduce the size of search spaces . . . . 187--192
William I. Gasarch On selecting the $k$ largest with
restricted quadratic queries . . . . . . 193--195
Ernst L. Leiss and
Hari N. Reddy Embedding complete binary trees into
hypercubes . . . . . . . . . . . . . . . 197--199
R. Shonkwiler Computing the Hausdorff set distance in
linear time for any $L_p$ point distance 201--207
J. M. Basart Some upper bounds for minimal trees . . 209--213
Jin-yi Cai and
Lane A. Hemachandra A note on enumerative counting . . . . . 215--219
Markku Sakkinen Selftype is a special case . . . . . . . 221--224
W. Rytter and
A. Saoudi On the complexity of the recognition of
parallel $2$D-image languages . . . . . 225--229
John Hershberger A new data structure for shortest path
queries in a simple polygon . . . . . . 231--235
Andrzej Lingas Bit complexity of matrix products . . . 237--242
Myoung Ho Kim and
Sakti Pramanik The FX distribution method for parallel
processing of partial match queries . . 243--252
Gerhard Woeginger On minimizing the sum of $k$ tardinesses 253--256
Susanne Hambrusch and
Michael Luby Parallel asynchronous connected
components in a mesh . . . . . . . . . . 257--263
T. Z. Kalamboukis and
S. L. Mantzaris Towards optimal distributed election on
chordal rings . . . . . . . . . . . . . 265--270
Farshad Fotouhi and
Sakti Pramanik Problem of optimizing the number of
block accesses in performing relational
join is NP-hard . . . . . . . . . . . . 271--275
Jiri Matousek Computing dominances in $E^n$ . . . . . 277--278
Timothy Law Snyder Corrigendum: ``Lower bounds for
rectilinear Steiner trees in bounded
space'' [Inform. Process. Lett. \bf
37(2), 31 January 1991, pp. 71--74] . . 279--279
Myung-Joon Lee and
Kwang-Moo Choe Corrigenda: ``${\rm SLR}(k)$ covering
for ${\rm LR}(k)$ grammars'' . . . . . . 281--281
Peter B. Danzig A cooperative game with applications to
computer networks . . . . . . . . . . . 283--289
Franco P. Preparata Inverting a Vandermonde matrix in
minimum parallel time . . . . . . . . . 291--294
Robert Kennedy Parallel cardinality stacks and an
application . . . . . . . . . . . . . . 295--299
Sandy Irani Two results on the list update problem 301--306
Kenneth Luo and
William Klostermeyer and
Yuan-Chieh Chow and
Richard Newman-Wolfe Optimal deadlock resolutions in
edge-disjoint reducible wait-for graphs 307--313
Shahram Latifi Distributed subcube identification
algorithms for reliable hypercubes . . . 315--321
Jerzy R. Nawrocki Conflict detection and resolution in a
lexical analyzer generator . . . . . . . 323--328
Kieran T. Herley A note on the token distribution problem 329--334
David Zuckerman On the time to traverse all edges of a
graph . . . . . . . . . . . . . . . . . 335--337
Dejan Zivkov