Last update:
Wed Jan 22 11:20:30 MST 2025
Bengt Aspvall and
Richard E. Stone Khachiyan's linear programming algorithm 1--13
Andrew Chi-Chih Yao An analysis of $(h, k, 1)$-Shellsort . . 14--50
Jon Louis Bentley A parallel algorithm for constructing
minimum spanning trees . . . . . . . . . 51--59
Louis Monier Combinatorial solutions of
multidimensional divide-and-conquer
recurrences . . . . . . . . . . . . . . 60--74
Ellis L. Johnson Subadditive lifting methods for
partitioning and knapsack problems . . . 75--96
Bengt Aspvall Recognizing disguised $NR(1)$ instances
of the satisfiability problem . . . . . 97--103
Paul Klingsberg A combinatorial family of labeled trees 104--106
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 107--110
Anonymous Editorial Board . . . . . . . . . . . . ??
P. Flajolet and
J. Françon and
J. Vuillemin Sequence of operations analysis for
dynamic data structures . . . . . . . . 111--141
J. C. Lagarias Worst-case complexity bounds for
algorithms in the theory of integral
quadratic forms . . . . . . . . . . . . 142--186
Persi Diaconis Average running time of the fast Fourier
transform . . . . . . . . . . . . . . . 187--208
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 209--212
Bruce Sagan On selecting a random shifted young
tableau . . . . . . . . . . . . . . . . 213--234
Witold Lipski, Jr. and
Franco P. Preparata Finding the contour of a union of
iso-oriented rectangies . . . . . . . . 235--246
Christine A. Morgan and
Peter J. Slater A linear algorithm for a core of a tree 247--258
Richard P. Brent and
Fred G. Gustavson and
David Y. Y. Yun Fast solution of Toeplitz systems of
equations and computation of Padé
approximants . . . . . . . . . . . . . . 259--295
V. Ya Pan Convolution of vectors over the real
field of constants by
evaluation-interpolation algorithms . . 297--300
Jon Louis Bentley and
James B. Saxe Decomposable searching problems I.
Static-to-dynamic transformation . . . . 301--358
Peter H. Sellers The theory and computation of
evolutionary distances: Pattern
recognition . . . . . . . . . . . . . . 359--373
Richard M. Karp and
Robert Endre Tarjan Linear expected-time algorithms for
connectivity problems . . . . . . . . . 374--393
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 394--395
Anonymous Author index for volume 1 . . . . . . . 396--396
Gideon Ehrlich Searching and sorting real numbers . . . 1--12
Jorge Olivos On vectorial addition chains . . . . . . 13--21
Shlomo Moran and
Yehoshua Perl The complexity of identifying redundant
and essential elements . . . . . . . . . 22--30
David A. Klarner An algorithm to determine when certain
sets have 0-density . . . . . . . . . . 31--43
Irvin Roy Hentzel and
Leslie Hogben Exhaustive checking of sparse algebras 44--49
A. Ralston A new memoryless algorithm for de Bruijn
sequences . . . . . . . . . . . . . . . 50--62
Witold Lipski, Jr. and
Franco P. Preparata Segments, rectangles, contours . . . . . 63--76
M. L. Fredman The spanning bound as a measure of range
query complexity . . . . . . . . . . . . 77--87
Yossi Shiloach and
Uzi Vishkin Finding the maximum, merging, and
sorting in a parallel computation model 88--102
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 103--104
Anonymous Erratum: Volume 1, Number 3 (1980),
``Finding the Contour of a Union of
Iso-Oriented Rectangles,'' by W. Lipski,
Jr., and France P. Preparata, pp.
235--246 . . . . . . . . . . . . . . . . 105--105
Anonymous Editorial Board . . . . . . . . . . . . ??
Yossi Shiloach Fast canonization of circular strings 107--121
T. C. Hu and
M. T. Shing An $O(n)$ algorithm to find a
near-optimum partition of a convex
polygon . . . . . . . . . . . . . . . . 122--138
R. Melville A time/space tradeoff for in-place array
permutation . . . . . . . . . . . . . . 139--143
V. Pan The bit-complexity of arithmetic
algorithms . . . . . . . . . . . . . . . 144--163
Judea Pearl A space-efficient on-line method of
computing quantile estimates . . . . . . 164--177
William H. Burge Stacks in a two-level store . . . . . . 178--185
H. El Gindy and
D. Avis A linear algorithm for computing the
visibility polygon from a point . . . . 186--197
R. Bar-Yehuda and
S. Even A linear-time approximation algorithm
for the weighted vertex cover problem 198--203
Herbert S. Wilf The uniform selection of free trees . . 204--207
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 208--210
Witold Lipski, Jr. and
Christos H. Papadimitriou A fast algorithm for testing for safety
and detecting deadlocks in locked
transaction systems . . . . . . . . . . 211--226
Lloyd Allison Generating coset representatives for
permutation groups . . . . . . . . . . . 227--244
Mark H. Overmars Dynamization of order decomposable set
problems . . . . . . . . . . . . . . . . 245--260
Ephraim Feig On systems of bilinear forms whose
minimal division-free algorithms are all
bilinear . . . . . . . . . . . . . . . . 261--281
Jan van Leeuwen and
Derick Wood The measure problem for rectangular
ranges in $d$-space . . . . . . . . . . 282--300
V. Pan A unified approach to the analysis of
bilinear algorithms . . . . . . . . . . 301--310
S. Even and
O. Goldreich The minimum-length generator sequence
problem is NP-hard . . . . . . . . . . . 311--313
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 314--315
Norishige Chiba and
Takao Nishizeki and
Nobuji Saito A linear 5-coloring algorithm of planar
graphs . . . . . . . . . . . . . . . . . 317--327
András Frank A weighted matroid intersection
algorithm . . . . . . . . . . . . . . . 328--336
D. T. Lee and
C. K. Wong Finding intersection of rectangles by
range search . . . . . . . . . . . . . . 337--347
Brenda S. Baker and
Donna J. Brown and
Howard P. Katseff A 54 algorithm for two-dimensional
packing . . . . . . . . . . . . . . . . 348--368
Peter Eades and
John Staples On optimal trees . . . . . . . . . . . . 369--384
David G. Cantor Irreducible polynomials with integral
coefficients have succinct certificates 385--392
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 393--405
Anonymous Author index for volume 2 . . . . . . . 406--406
J. Michael Steele and
Andrew C. Yao Lower bounds for algebraic decision
trees . . . . . . . . . . . . . . . . . 1--8
Selim G. Akl and
Henk Meijer On the average-case complexity of
``bucketing'' algorithms . . . . . . . . 9--13
Danny Dolev The Byzantine generals strike again . . 14--30
R. Tolimieri A nonquadratic minimal algorithm for a
system of quadratic forms . . . . . . . 31--40
Paul Klingsberg A Gray code for compositions . . . . . . 41--44
Oscar H. Ibarra and
Shlomo Moran and
Roger Hui A generalization of the fast $LUP$
matrix decomposition algorithm and
applications . . . . . . . . . . . . . . 45--56
Yossi Shiloach and
Uzi Vishkin An $O(\log n)$ parallel connectivity
algorithm . . . . . . . . . . . . . . . 57--67
Michael L. Fredman and
Dennis J. Volper The complexity of partial match
retrieval in a dynamic setting . . . . . 68--78
Martin Aigner Parallel complexity of sorting problems 79--88
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 89--99
Anonymous Editorial Board . . . . . . . . . . . . ??
C. P. Schnorr Refined analysis and improvements on
some factoring algorithms . . . . . . . 101--127
Yossi Shiloach and
Uzi Vishkin An $O(n^2 \log n)$ parallel max-flow
algorithm . . . . . . . . . . . . . . . 128--146
Robert N. Goldberg Minimal string difference encodings . . 147--156
Costas S. Iliopoulos Analysis of an algorithm for composition
of binary quadratic forms . . . . . . . 157--159
V. K. Vaishnavi and
D. Wood Rectilinear line segment intersection,
layered segment trees, and dynamization 160--176
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 177--181
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 182--195
Maurice Mignotte Identification of algebraic numbers . . 197--204
Barry K. Rosen Robust linear algorithms for cutsets . . 205--217
D. T. Lee and
F. P. Preparata An improved algorithm for the rectangle
enclosure problem . . . . . . . . . . . 218--224
Karl J. Lieberherr Algorithmic extremal problems in
combinatorial optimization . . . . . . . 225--244
Danny Dolev and
Maria Klawe and
Michael Rodeh An $O(n \log n)$ unidirectional
distributed algorithm for extrema
finding in a circle . . . . . . . . . . 245--260
Jeffrey Scott Vitter Deletion algorithms for hashing that
preserve randomness . . . . . . . . . . 261--275
Gary D. Knott Fixed-bucket binary storage trees . . . 276--287
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 288--300
Anonymous Corrigendum . . . . . . . . . . . . . . 301--302
B. S. Baker and
E. G. Coffman, Jr. A two-dimensional bin-packing model of
preemptive, FIFO storage allocation . . 303--316
D. S. Franzblau and
Doron Zeilberger A bijective proof of the hook-length
formula . . . . . . . . . . . . . . . . 317--343
Kazuo Nakajima and
S. Louis Hakimi Complexity results for scheduling tasks
with discrete starting times . . . . . . 344--361
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 362--380
David S. Johnson The NP-completeness column: an ongoing
gulde . . . . . . . . . . . . . . . . . 381--395
Anonymous Author index for volume 3 . . . . . . . 396--396
V. Ya Pan The additive and logical complexities of
linear and bilinear arithmetic
algorithms . . . . . . . . . . . . . . . 1--34
Daniel Leven and
Zvi Galil NP completeness of finding the chromatic
index of regular graphs . . . . . . . . 35--44
Uzi Vishkin Implementation of simultaneous memory
address access in models that forbid it 45--50
U. I. Gupta and
D. T. Lee and
C. K. Wong Ranking and unranking of $B$-trees . . . 51--60
Greg N. Frederickson and
Donald B. Johnson Finding $k$th paths and $p$-centers by
generating and searching good data
structures . . . . . . . . . . . . . . . 61--80
Ephraim Feig Minimal algorithms for bilinear forms
may have divisions . . . . . . . . . . . 81--84
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 85--86
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 87--100
Anonymous Editorial Board . . . . . . . . . . . . ??
Ronald I. Becker and
Yehoshua Perl Shifting algorithms for tree
partitioning with general weighting
functions . . . . . . . . . . . . . . . 101--120
Binay K. Bhattacharya and
Godfried T. Toussaint Efficient algorithms for computing the
maximum distance between two finite
planar sets . . . . . . . . . . . . . . 121--136
Ephraim Feig Certain systems of bilinear forms whose
minimal algorithms are all quadratic . . 137--149
Alan D. Kalvin and
Yaakov L. Varol On the generation of all topological
sortings . . . . . . . . . . . . . . . . 150--162
Gregory Butler Computing normalizers in permutation
groups . . . . . . . . . . . . . . . . . 163--175
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 176--188
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 189--203
John D. Dixon and
Herbert S. Wilf The random selection of unlabeled graphs 205--213
A. Guénoche Random spanning tree . . . . . . . . . . 214--220
W. M. Beynon A formal account of some elementary
continued fraction algorithms . . . . . 221--240
T. C. Hu and
M. T. Shing Multiterminal flows in outerplanar
networks . . . . . . . . . . . . . . . . 241--261
Errol L. Lloyd An $O(n \log m)$ algorithm for the
Josephus Problem . . . . . . . . . . . . 262--270
Eliezer L. Lozinskii An algorithm for parallel evaluation of
functions . . . . . . . . . . . . . . . 271--281
C. Pandu Rangan On the minimum number of additions
required to compute a quadratic form . . 282--285
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 286--300
Anonymous Corrigendum . . . . . . . . . . . . . . 301--301
Pavol Hell and
Moshe Rosenfeld The complexity of finding generalized
paths in tournaments . . . . . . . . . . 303--309
Hiroshi Imai and
Takao Asano Finding the connected components and a
maximum clique of an intersection graph
of rectangles in the plane . . . . . . . 310--323
Ronald L. Graham and
F. Frances Yao Finding the convex hull of a simple
polygon . . . . . . . . . . . . . . . . 324--331
Paul Pritchard Fast compact prime number sieves (among
others) . . . . . . . . . . . . . . . . 332--344
Edward Minieka and
Niranjani H. Patel On finding the core of a tree with a
specified length . . . . . . . . . . . . 345--352
Ten-Hwang Lai and
Sartaj Sahni Nearly on-line scheduling of
multiprocessor systems with memories . . 353--362
Jean Pierre Duval Factorizing words over an ordered
alphabet . . . . . . . . . . . . . . . . 363--381
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 382--396
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 397--411
Anonymous Author index for volume 4 . . . . . . . 412--412
Dan Gusfield Bounds for naive multiple machine
scheduling with release times and
deadlines . . . . . . . . . . . . . . . 1--6
Gary D. Knott Direct-chaining with coalescing lists 7--21
Joseph Y.-T Leung Fast algorithms for generating all
maximal independent sets of interval,
circular-arc and chordal graphs . . . . 22--35
Per-Åke Larson Analysis of hashing with chaining in the
prime area . . . . . . . . . . . . . . . 36--47
Danny Dolev and
Manfred K. Warmuth Scheduling precedence graphs of bounded
height . . . . . . . . . . . . . . . . . 48--59
Alan Tucker and
Donna Wilson An $O(N^2)$ algorithm for coloring
perfect planar graphs . . . . . . . . . 60--68
Shou-Hsuan Stephen Huang and
C. K. Wong Optimal binary split trees . . . . . . . 69--79
Harold N. Gabow and
Robert E. Tarjan Efficient algorithms for a family of
matroid intersection problems . . . . . 80--131
P. Ramanan and
J. S. Deogun and
C. L. Liu A personnel assignment problem . . . . . 132--144
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 145--146
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 147--160
Anonymous Papers to appear in forthcoming issues 161--162
Anonymous Editorial Board . . . . . . . . . . . . ??
David A. Plaisted Heuristic matching for graphs satisfying
the triangle inequality . . . . . . . . 163--179
P. J. Weinberger Finding the number of factors of a
polynomial . . . . . . . . . . . . . . . 180--186
M. Boshernitzan and
A. S. Fraenkel A linear algorithm for nonhomogeneous
spectra of numbers . . . . . . . . . . . 187--198
Eljas Soisalon-Soininen and
Derick Wood Optimal algorithms to compute the
closure of a set of iso-rectangles . . . 199--214
R. P. Anstee and
Martin Farber Characterizations of totally balanced
matrices . . . . . . . . . . . . . . . . 215--230
Christos H. Papadimitriou and
Umesh V. Vazirani On two geometric problems related to the
travelling salesman problem . . . . . . 231--246
Nicholas C. Wormald Generating random regular graphs . . . . 247--280
Ichiro Semba An efficient algorithm for generating
all $k$-subsets $(1 \leq k \leq m \leq
n)$ of the set $[1, 2,\ldots{}, n]$ in
lexicographical order . . . . . . . . . 281--283
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 284--299
Anonymous Papers to appear in forthcoming issues 300--301
Ralf Hartmut Güting An optimal contour algorithm for
iso-oriented rectangles . . . . . . . . 303--326
G. Seroussi and
A. Lempel On symmetric algorithms for bilinear
forms over finite fields . . . . . . . . 327--344
Derek Corneil and
Mark Goldberg A non-factorial algorithm for canonical
numbering of a graph . . . . . . . . . . 345--362
L. G. Valiant Short monotone formulae for the majority
function . . . . . . . . . . . . . . . . 363--366
Yehoshua Perl Optimum split trees . . . . . . . . . . 367--374
Pierre Rosenstiehl and
Robert E. Tarjan Gauss codes, planar Hamiltonian graphs,
and stack-sortable permutations . . . . 375--390
John R. Gilbert and
Joan P. Hutchinson and
Robert Endre Tarjan A separator theorem for graphs of
bounded genus . . . . . . . . . . . . . 391--407
T. Lengauer On the solution of inequality systems
relevant to IC-layout . . . . . . . . . 408--421
Michael G. Main and
Richard J. Lorentz An $O(n \log n)$ algorithm for finding
all repetitions in a string . . . . . . 422--432
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 433--447
Anonymous Papers to appear in forthcoming issues 448--449
Gaston H. Gonnet and
J. Ian Munro The analysis of linear probing sort by
the use of a new mathematical transform 451--470
J. B. Remmel and
R. Whitney Multiplying Schur functions . . . . . . 471--487
Eli Shamir and
Eli Upfal Sequential and distributed graph
coloring algorithms with performance
analysis in random graph spaces . . . . 488--501
S. F. Assmann and
D. S. Johnson and
D. J. Kleitman and
J. Y.-T Leung On a dual version of the one-dimensional
bin packing problem . . . . . . . . . . 502--525
S. Louis Hakimi and
Edward F. Schmeichel An adaptive algorithm for system level
diagnosis . . . . . . . . . . . . . . . 526--530
Eitan M. Gurari and
Ivan Hal Sudborough Improved dynamic programming algorithms
for bandwidth minimization and the
MinCut Linear Arrangement problem . . . 531--546
Micha Hofri A probabilistic analysis of the Next-Fit
bin packing algorithm . . . . . . . . . 547--556
Prakash V. Ramanan and
Laurent Hyafil New algorithms for selection . . . . . . 557--578
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 579--594
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 595--609
Anonymous Papers to appear in forthcoming issues 610--611
Anonymous Author index for volume 5 . . . . . . . 612--613
Luc Devroye The expected length of the longest probe
sequence for bucket searching when the
distribution is not uniform . . . . . . 1--9
Z. Miller and
J. B. Orlin NP-completeness for minimizing maximum
edge length in grid embeddings . . . . . 10--16
Garret Swart Finding the convex hull facet by facet 17--48
Brenda S. Baker A new proof for the first-fit decreasing
bin-packing algorithm . . . . . . . . . 49--70
Valery B. Alekseyev On the complexity of some algorithms of
matrix multiplication . . . . . . . . . 71--85
N. Linial and
M. Saks Searching ordered structures . . . . . . 86--103
Colm Ó'Dúnlaing and
Chee K. Yap A ``retraction'' method for planning the
motion of a disc . . . . . . . . . . . . 104--111
R. P. Anstee An algorithmic proof of Tutte's
$f$-factor theorem . . . . . . . . . . . 112--131
Esko Ukkonen Finding approximate patterns in strings 132--137
Markku Tamminen Two levels are as good as any . . . . . 138--144
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 145--159
Anonymous Papers to appear in forthcoming issues 160--161
Anonymous Editorial Board . . . . . . . . . . . . ??
Donald E. Knuth Dynamic Huffman coding . . . . . . . . . 163--180
Donald E. Knuth An analysis of optimum caching . . . . . 181--199
Quentin F. Stout Pyramid computer solutions of the
closest pair problem . . . . . . . . . . 200--212
H. Edelsbrunner Computing the extreme distances between
two convex polygons . . . . . . . . . . 213--224
Andrzej Proskurowski and
Frank Ruskey Binary tree gray codes . . . . . . . . . 225--238
Fanica Gavril and
Johanan Schönheim Constructing trees with prescribed
cardinalities for the components of
their vertex deleted subgraphs . . . . . 239--252
Andrew C. Yao On optimal arrangements of keys with
double hashing . . . . . . . . . . . . . 253--264
Refael Hassin and
Nimrod Megiddo An optimal algorithm for finding all the
jumps of a monotone step-function . . . 265--274
Edward A. Bender and
Herbert S. Wilf A theoretical analysis of backtracking
in the graph coloring problem . . . . . 275--282
Leo J. Guibas Problems . . . . . . . . . . . . . . . . 283--290
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 291--305
Anonymous Papers to appear in forthcoming issues 306--307
Martin Farber and
J. Mark Keil Domination in permutation graphs . . . . 309--321
Thomas G. Szymanski Hash table reorganization . . . . . . . 322--335
Patricio V. Poblete and
J. Ian Munro The analysis of a fringe heuristic for
binary search trees . . . . . . . . . . 336--350
M. C. Er The complexity of the generalised cyclic
Towers of Hanoi problem . . . . . . . . 351--358
Victor Klee and
Michael C. Laskowski Finding the smallest triangles
containing a given convex polygon . . . 359--375
Peter B. Borwein On the complexity of calculating
factorials . . . . . . . . . . . . . . . 376--380
David P. Dobkin and
David G. Kirkpatrick A linear algorithm for determining the
separation of convex polyhedra . . . . . 381--392
Hiroyuki Nakayama and
Takao Nishizeki and
Nobuji Saito Lower bounds for combinatorial problems
on graphs . . . . . . . . . . . . . . . 393--399
Kohei Noshita A theorem on the expected complexity of
Dijkstra's shortest path algorithm . . . 400--408
Alon Itai and
Michael Rodeh Scheduling transmissions in a network 409--429
Nimrod Megiddo Partitioning with two lines in the plane 430--433
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 434--451
Anonymous Papers to appear in forthcoming issues 452--453
David P. Dobkin and
J. Ian Munro Efficient uses of the past . . . . . . . 455--465
Béla Bollobás and
Istvan Simon Repeated random insertion into a
priority queue . . . . . . . . . . . . . 466--477
William M. Kantor Polynomial-time algorithms for finding
elements of prime order and Sylow
subgroups . . . . . . . . . . . . . . . 478--514
Herbert Edelsbrunner and
Mark H. Overmars Batched dynamic solutions to
decomposable searching problems . . . . 515--542
B. Domanski and
M. Anshel The complexity of Dehn's algorithm for
word problems in groups . . . . . . . . 543--549
A. Bagchi and
P. K. Srimani Weighted heuristic search in networks 550--576
Robert W. Irving An efficient algorithm for the ``stable
roommates'' problem . . . . . . . . . . 577--595
Anonymous Papers to appear in forthcoming issues 596--596
Anonymous Author index for volume 6 . . . . . . . 597--598
Marinus Veldhorst The optimal representation of disjoint
iso-oriented rectangles in
two-dimensional trees . . . . . . . . . 1--34
D. K. Friesen and
M. A. Langston Evaluation of a MULTIFIT-based
scheduling algorithm . . . . . . . . . . 35--59
Mark Jerrum A compact representation for permutation
groups . . . . . . . . . . . . . . . . . 60--78
Dorit S. Hochbaum and
Takao Nishizeki and
David B. Shmoys A better than ``best possible''
algorithm to edge color multigraphs . . 79--104
Prasoon Tiwari An efficient parallel algorithm for
shifting the root of a depth first
spanning tree . . . . . . . . . . . . . 105--119
Miroslawa Skowro\'nska and
Maciej M. Syslo and
Cristina Zamfirescu An algorithmic characterization of total
digraphs . . . . . . . . . . . . . . . . 120--133
Esther M. Arkin and
Christos H. Papadimitriou On the complexity of circulations . . . 134--145
Ouri Wolfson An algorithm for early unlocking of
entities in database transactions . . . 146--156
Anonymous Papers to appear in forthcoming issues 157--157
Anonymous Editorial Board . . . . . . . . . . . . ??
Robert Sedgewick A new upper bound for Shellsort . . . . 159--173
M. E. Dyer and
A. M. Frieze Planar $3$DM is NP-complete . . . . . . 174--184
Marc Snir Depth-size trade-offs for parallel
prefix computation . . . . . . . . . . . 185--201
Richard Cole Searching and storing similar lists . . 202--220
Takao Asano and
Tetsuo Asano and
Ron Y. Pinter Polygon triangulation: Efficiency and
minimality . . . . . . . . . . . . . . . 221--231
Raghunath Raghavan and
James Cohoon and
Sartaj Sahni Single bend wiring . . . . . . . . . . . 232--257
Joseph O'Rourke and
Alok Aggarwal and
Sanjeev Maddila and
Michael Baldwin An optimal algorithm for finding minimal
enclosing triangles . . . . . . . . . . 258--269
Max L. Warshauer Conway's parallel sorting algorithm . . 270--276
Michael Werman and
Shmuel Peleg and
Robert Melter and
T. Y. Kong Bipartite graph matching for points on a
line or a circle . . . . . . . . . . . . 277--284
Mikhail J. Atallah Computing the convex hull of line
intersections . . . . . . . . . . . . . 285--288
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 289--305
Anonymous Papers to appear in forthcoming issues 306--307
Neil Robertson and
P. D. Seymour Graph minors. II. Algorithmic aspects of
tree-width . . . . . . . . . . . . . . . 309--322
J. L. Lewandowski and
C. L. Liu and
J. W. S. Liu An algorithmic proof of a generalization
of the Birkhoff--von Neumann theorem . . 323--330
Tuvi Etzion An algorithm for constructing $m$-ary de
Bruijn sequences . . . . . . . . . . . . 331--340
Mai Thanh and
V. S. Alagar and
T. D. Bui Optimal expected-time algorithms for
merging . . . . . . . . . . . . . . . . 341--357
Nimrod Megiddo and
Eitan Zemel An $O(n \log n)$ randomizing algorithm
for the weighted Euclidean 1-center
problem . . . . . . . . . . . . . . . . 358--368
Alok Aggarwal and
Robert C. Melville Fast computation of the modality of
polygons . . . . . . . . . . . . . . . . 369--381
Dana Richards Finding short cycles in planar graphs
using separators . . . . . . . . . . . . 382--394
Keith Brinck On deletion in threaded binary trees . . 395--411
J. H. Hester and
D. S. Hirschberg and
S.-H. S. Huang and
C. K. Wong Faster construction of optimal binary
split trees . . . . . . . . . . . . . . 412--424
J. M. Robson Algorithms for maximum independent sets 425--440
Michael S. Paterson and
F. Frances Yao Point retrieval for polygons . . . . . . 441--447
Anonymous Papers to appear in forthcoming issues 448--448
Ker-I Ko and
Shia-Chung Teng On the number of queries necessary to
identify a permutation . . . . . . . . . 449--462
Philippe Flajolet and
Nasser Saheb The complexity of generating an
exponentially distributed variate . . . 463--488
Micha Hofri and
Sami Kamhi A stochastic analysis of the NFD
bin-packing algorithm . . . . . . . . . 489--509
Michael Kaufmann and
Kurt Mehlhorn Routing through a generalized switchbox 510--531
B. S. Baker and
S. J. Fortune and
S. R. Mahaney Polygon containment under translation 532--548
Pawel Winter Generalized Steiner problem in
series-parallel networks . . . . . . . . 549--566
Noga Alon and
László Babai and
Alon Itai A fast and simple randomized parallel
algorithm for the maximal independent
set problem . . . . . . . . . . . . . . 567--583
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 584--601
Anonymous Papers to appear in forthcoming issues 602--602
Anonymous Author index for volume 7 . . . . . . . 603--604
Hiroshi Imai and
Takao Asano Dynamic orthogonal segment intersection
search . . . . . . . . . . . . . . . . . 1--18
Richard Cole and
Chee K. Yap Shape from probing . . . . . . . . . . . 19--38
Howard J. Karloff and
David B. Shmoys Efficient parallel algorithms for edge
coloring problems . . . . . . . . . . . 39--52
Jan K. Pachl A lower bound for probabilistic
distributed algorithms . . . . . . . . . 53--65
Alejandro A. Schäffer and
Christopher J. Van Wyk Convex hulls of piecewise-smooth Jordan
curves . . . . . . . . . . . . . . . . . 66--94
George Steiner Searching in 2-dimensional partial
orders . . . . . . . . . . . . . . . . . 95--105
Moon Jung Chung $O(n^{2.5})$ time algorithms for the
subgraph homeomorphism problem on trees 106--112
John L. Mohammed and
Carlos S. Subi An improved block-interchange algorithm 113--121
George Georgakopoulos and
Christos H. Papadimitriou The $1$-Steiner tree problem . . . . . . 122--130
Helaman R. P. Ferguson A noninductive ${\rm GL}(n, Z)$
algorithm that constructs integral
linear relations for $n$ $Z$-linearly
dependent real numbers . . . . . . . . . 131--145
Shou-Hsuan Stephen Huang Optimal multiway split trees . . . . . . 146--156
Anonymous Papers to appear in forthcoming issues 157--157
Anonymous Editorial Board . . . . . . . . . . . . ??
M. D. Atkinson An optimal algorithm for geometrical
congruence . . . . . . . . . . . . . . . 159--172
J. C. Lagarias and
A. M. Odlyzko Computing $\pi(x)$: an analytic method 173--191
Daniel Leven and
Micha Sharir An efficient and simple motion planning
algorithm for a ladder amidst polygonal
barriers . . . . . . . . . . . . . . . . 192--215
M. W. Bern and
E. L. Lawler and
A. L. Wong Linear-time computation of optimal
subgraphs of decomposable graphs . . . . 216--235
B. Pittel Linear probing: the probable largest
search time grows logarithmically with
the number of records . . . . . . . . . 236--249
V. Rödl and
C. Tovey Multiple optima in local search . . . . 250--259
T. Lengauer Efficient algorithms for finding minimum
spanning forests of hierarchically
defined graphs . . . . . . . . . . . . . 260--284
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 285--303
Anonymous Papers to appear in forthcoming issues 304--304
Dorit S. Hochbaum and
Wolfgang Maass Fast approximation algorithms for a
nonconvex covering problem . . . . . . . 305--323
S. P. Tung Computational complexities of
Diophantine equations with parameters 324--336
N. Alon and
Z. Galil and
V. D. Milman Better expanders and superconcentrators 337--347
David P. Dobkin and
Herbert Edelsbrunner Space searching for intersecting objects 348--361
Donald W. Loveland Finding critical sets . . . . . . . . . 362--371
Ten-Hwang Lai and
Alan Sprague On the routability of a convex grid . . 372--384
Stephen A. Cook and
Pierre McKenzie Problems complete for deterministic
logarithmic space . . . . . . . . . . . 385--394
Michael F. Bridgland Universal traversal sequences for paths
and cycles . . . . . . . . . . . . . . . 395--404
David A. Plaisted and
Jiarong Hong A heuristic triangulation algorithm . . 405--437
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 438--448
Anonymous Papers to appear in forthcoming issues 449--449
Janet A. Blumer How much is that DAWG in the window? A
moving window algorithm for the directed
acyclic word graph . . . . . . . . . . . 451--469
Joan F. Boyar and
Howard J. Karloff Coloring planar graphs in parallel . . . 470--479
Mikhail J. Atallah and
Susanne E. Hambrusch On bipartite matchings of minimum
density . . . . . . . . . . . . . . . . 480--502
Joan M. Lucas The rotation graph of binary trees is
Hamiltonian . . . . . . . . . . . . . . 503--535
Ouri Wolfson The virtues of locking by symbolic names 536--556
Jeffrey Salowe and
William Steiger Simplified stable merging tasks . . . . 557--571
Shankar M. Venkatesan Improved constants for some separator
theorems . . . . . . . . . . . . . . . . 572--578
Lawrence L. Larmore A subquadratic algorithm for
constructing approximately optimal
binary search trees . . . . . . . . . . 579--591
F\uanic\ua Gavril Generating the maximum spanning trees of
a weighted graph . . . . . . . . . . . . 592--597
Anonymous Papers to appear in forthcoming issues 598--599
Anonymous Author index for volume 8 . . . . . . . 600--601
W. M. Kantor and
D. E. Taylor Polynomial-time versions of Sylow's
theorem . . . . . . . . . . . . . . . . 1--17
John Hershberger and
Leonidas J. Guibas An $O(n^2)$ shortest path algorithm for
a non-rotating convex body . . . . . . . 18--46
C. P. Schnorr A more efficient algorithm for lattice
basis reduction . . . . . . . . . . . . 47--62
Jonathan S. Turner Almost all $k$-colorable graphs are easy
to color . . . . . . . . . . . . . . . . 63--82
Mauricio Karchmer and
Joseph Naor A fast parallel algorithm to color a
graph with $\Delta$ colors . . . . . . . 83--91
Xin He and
Yaacov Yesha Binary tree algebraic computation and
parallel algorithms for simple graphs 92--113
Charles E. Leiserson and
James B. Saxe A mixed-integer linear programming
problem which is efficiently solvable 114--128
Feffrey H. Kingston A new proof of the Garsia--Wachs
algorithm . . . . . . . . . . . . . . . 129--136
Michael Kaminski An algorithm for polynomial
multiplication that does not depend on
the ring constants . . . . . . . . . . . 137--147
Anonymous Papers to appear in forthcoming issues 148--149
Anonymous Editorial Board . . . . . . . . . . . . ??
F. Aurenhammer Improved algorithms for discs and balls
using power diagrams . . . . . . . . . . 151--161
Frank Ruskey Adjacent interchange generation of
combinations . . . . . . . . . . . . . . 162--180
A. M. Frieze An algorithm for finding Hamilton cycles
in random directed graphs . . . . . . . 181--204
Danny Soroker Fast parallel strong orientation of
mixed graphs and related augmentation
problems . . . . . . . . . . . . . . . . 205--223
Wojciech Szpankowski Some results on $V$-ary asymmetric tries 224--244
J. H. Hester and
D. S. Hirschberg and
L. L. Larmore Construction of optimal binary split
trees in the presence of bounded access
probabilities . . . . . . . . . . . . . 245--253
Mark H. Overmars Efficient data structures for range
searching on a grid . . . . . . . . . . 254--275
Danny Soroker Fast parallel algorithms for finding
Hamiltonian paths and cycles in a
tournament . . . . . . . . . . . . . . . 276--286
Manfred Kunde and
Michael A. Langston and
Jin-Ming Liu On a special case of uniform processor
scheduling . . . . . . . . . . . . . . . 287--296
Anonymous Papers to appear in forthcoming issues 297--298
Vijaya Ramachandran Finding a minimum feedback arc set in
reducible flow graphs . . . . . . . . . 299--313
Martin Charles Golumbic and
Peter L. Hammer Stability in circular arc graphs . . . . 314--320
Alejandro A. Schäffer A tighter upper bound on the worst case
behavior of Conway's parallel sorting
algorithm . . . . . . . . . . . . . . . 321--342
Harold Greenberg Solution to a linear Diophantine
equation for nonnegative integers . . . 343--353
Michael Kaminski and
David G. Kirkpatrick and
Nader H. Bshouty Addition requirements for matrix and
transposed matrix products . . . . . . . 354--364
A. Schönhage Probabilistic computation of integer
polynomial GCDs . . . . . . . . . . . . 365--371
Mark H. Overmars and
Derick Wood On rectangular visibility . . . . . . . 372--390
Lajos Rónyai Factoring polynomials over finite fields 391--400
Ying Cheng and
Frank K. Hwang Diameters of weighted double loop
networks . . . . . . . . . . . . . . . . 401--410
Harold N. Gabow and
Robert E. Tarjan Algorithms for two bottleneck
optimization problems . . . . . . . . . 411--417
Robert Wilber The concave least-weight subsequence
problem revisited . . . . . . . . . . . 418--425
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 426--444
Anonymous Papers to appear in forthcoming issues 445--447
B. K. Bhattacharya and
J. Zorbas Solving the two-dimensional findpath
problem using a line-triangle
representation of the robot . . . . . . 449--469
Hanoch Levy and
David W. Low A contraction algorithm for finding
small cycle cutsets . . . . . . . . . . 470--493
Lajos Rónyai Zero divisors in quaternion algebras . . 494--506
J. Cheriyan and
S. N. Maheshwari Finding nonseparating induced cycles and
independent spanning trees in
3-connected graphs . . . . . . . . . . . 507--537
Ingo Althöfer On the complexity of searching game
trees and other recursion trees . . . . 538--567
Reuven Bar-Yehuda and
Shay Kutten Fault tolerant distributed majority
commitment . . . . . . . . . . . . . . . 568--582
Oded Maimon An algorithm for the Lorenz measure in
locational decisions on trees . . . . . 583--596
S. Olariu and
S. Toida and
M. Zubair On a conjecture by Plaisted and Hong . . 597--598
Anonymous Papers to appear in forthcoming issues 599--600
Anonymous Author index for volume 9 . . . . . . . 601--602
Steven Minsker The Towers of Hanoi rainbow problem:
Coloring the rings . . . . . . . . . . . 1--19
Gary D. Knott and
Pilar de la Torre Hash table collision resolution with
direct chaining . . . . . . . . . . . . 20--34
Marek Chrobak and
Moti Yung Fast algorithms for edge-coloring planar
graphs . . . . . . . . . . . . . . . . . 35--51
Hosam M. Mahmoud and
Boris Pittel Analysis of the space of search trees
under the random insertion algorithm . . 52--75
Yishay Mansour and
Baruch Schieber Finding the edge connectivity of
directed graphs . . . . . . . . . . . . 76--85
Yukon Chang and
Susanne Hambrusch and
Janos Simon On the computational complexity of
continuous routing . . . . . . . . . . . 86--108
Ellen B. Feinberg and
Christos H. Papadimitriou Finding feasible paths for a two-point
body . . . . . . . . . . . . . . . . . . 109--119
David Bernstein and
Michael Rodeh and
Izidor Gertner Approximation algorithms for scheduling
arithmetic expressions on pipelined
machines . . . . . . . . . . . . . . . . 120--139
R. Cypher and
J. L. C. Sanz and
L. Snyder Hypercube and shuffle-exchange
algorithms for image component labeling 140--150
Yahya Ould Hamidoune and
David Roeder and
Steven Janke and
Todd Feil and
Richard Koo The probability of splitters in a list 151--154
Anonymous Papers to appear in forthcoming issues 155--156
Anonymous Editorial Board . . . . . . . . . . . . ??
Gad M. Landau and
Uzi Vishkin Fast parallel and serial approximate
string matching . . . . . . . . . . . . 157--169
Ralf-Hartmut Güting and
Otto Nurmi and
Thomas Ottmann Fast algorithms for direct enclosures
and direct dominances . . . . . . . . . 170--186
Norishige Chiba and
Takao Nishizeki The Hamiltonian cycle problem is
linear-time solvable for 4-connected
planar graphs . . . . . . . . . . . . . 187--211
H. Heusinger and
H. Noltemeier On separable clusterings . . . . . . . . 212--227
Patricio V. Poblete and
J. Ian Munro Last-come-first-served hashing . . . . . 228--248
Gerard A. P. Kindervater and
Jan Karel Lenstra and
David B. Shmoys The parallel complexity of TSP
heuristics . . . . . . . . . . . . . . . 249--270
Charles J. Colbourn and
Robert P. J. Day and
Louis D. Nel Unranking and ranking spanning trees of
a graph . . . . . . . . . . . . . . . . 271--286
K. Abrahamson and
N. Dadoun and
D. G. Kirkpatrick and
T. Przytycka A simple parallel tree contraction
algorithm . . . . . . . . . . . . . . . 287--302
Anonymous Papers to appear in forthcoming issues 303--304
Prakash Ramanan and
Donna J. Brown and
C. C. Lee and
D. T. Lee On-line bin packing in linear time . . . 305--326
Michael T. Goodrich Triangulating a polygon in parallel . . 327--351
C. J. H. McDiarmid and
B. A. Reed Building heaps fast . . . . . . . . . . 352--365
Renzo Sprugnoli The analysis of a simple in-place
merging algorithm . . . . . . . . . . . 366--380
David Fernández-Baca and
Giora Slutzki Solving parametric problems on trees . . 381--402
F. Bergeron and
J. Berstel and
S. Brlek and
C. Duboc Addition chains using continued
fractions . . . . . . . . . . . . . . . 403--412
Nancy Amato and
Manuel Blum and
Sandra Irani and
Ronitt Rubinfeld Reversing trains: a turn of the century
sorting problem . . . . . . . . . . . . 413--428
Richard M. Karp and
Michael Luby and
Neal Madras Monte--Carlo approximation algorithms
for enumeration problems . . . . . . . . 429--448
Anonymous Papers to appear in forthcoming issues 449--450
M. E. Dyer and
A. M. Frieze The solution of some random NP-hard
problems in polynomial expected time . . 451--489
Ching-Tsun Chou and
Inder S. Gopal Linear broadcast routing . . . . . . . . 490--517
Michelle L. Wachs On an efficient dynamic programming
technique of F. F. Yao . . . . . . . . . 518--530
James Lee Hafner and
Kevin S. McCurley On the distribution of running times of
certain integer factoring algorithms . . 531--556
Michael O. Rabin and
Vijay V. Vazirani Maximum matchings in general graphs
through randomization . . . . . . . . . 557--567
Carsten Thomassen The graph genus problem is NP-complete 568--576
Carla D. Savage Gray code sequences of partitions . . . 577--595
Anonymous Papers to appear in forthcoming issues 596--597
Anonymous Author index for volume 10 . . . . . . . 598--599
H. Everett and
D. G. Corneil Recognizing visibility graphs of spiral
polygons . . . . . . . . . . . . . . . . 1--26
Liwu Li and
T. A. Marsland Probability-based game tree pruning . . 27--43
Yuejiang Huang A new algorithm for the generation of
binary de Bruijn sequences . . . . . . . 44--51
Brendan D. McKay and
Nicholas C. Wormald Uniform generation of random regular
graphs of moderate degree . . . . . . . 52--67
Frank Ruskey and
Andrzej Proskurowski Generating binary trees by
transpositions . . . . . . . . . . . . . 68--84
David Eppstein Sequence comparison with mixed convex
and concave costs . . . . . . . . . . . 85--101
Marek Chrobak and
Takao Nishizeki Improved edge-coloring algorithms for
planar graphs . . . . . . . . . . . . . 102--116
H. R. Morton and
H. B. Short Calculating the 2-variable polynomial
for knots presented as closed braids . . 117--131
Joseph Naor and
Mark B. Novick An efficient reconstruction of a graph
from its line graph in parallel . . . . 132--143
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 144--151
Anonymous Papers to appear in forthcoming issues 152--152
Anonymous Editorial Board . . . . . . . . . . . . ??
Fran Berman and
David Johnson and
Tom Leighton and
Peter W. Shor and
Larry Snyder Generalized planar matching . . . . . . 153--184
V. G. Kulkarni Generating random combinatorial objects 185--207
Mark S. Manasse and
Lyle A. McGeoch and
Daniel D. Sleator Competitive algorithms for server
problems . . . . . . . . . . . . . . . . 208--230
E. Schmeichel and
S. L. Hakimi and
M. Otsuka and
G. Sullivan A parallel fault identification
algorithm . . . . . . . . . . . . . . . 231--241
Mark Allen Weiss and
Robert Sedgewick Tight lower bounds for Shellsort . . . . 242--251
Gur Saran Adhar and
Shietung Peng Parallel algorithms for cographs and
parity graphs with applications . . . . 252--284
Eytan Ronn NP-complete stable matching problems . . 285--304
Anonymous Papers to appear in forthcoming issues 305--305
Baruch Awerbuch and
Amotz Bar-Noy and
Nathan Linial and
David Peleg Improved routing strategies with
succinct tables . . . . . . . . . . . . 307--341
Baruch Awerbuch On the effects of feedback in dynamic
network protocols . . . . . . . . . . . 342--373
Gil Neiger and
Sam Toueg Automatically increasing the
fault-tolerance of distributed
algorithms . . . . . . . . . . . . . . . 374--419
Ofer Biran and
Shlomo Moran and
Shmuel Zaks A combinatorial characterization of the
distributed 1-solvable tasks . . . . . . 420--440
James Aspnes and
Maurice Herlihy Fast randomized consensus using shared
memory . . . . . . . . . . . . . . . . . 441--461
David B. Johnson and
Willy Zwaenepoel Recovery in distributed systems using
optimistic message logging and
checkpointing . . . . . . . . . . . . . 462--491
Ming-Deh A. Huang and
Shang-Hua Teng Security, verifiability, and
universality in distributed computing 492--521
Anonymous Papers to appear in forthcoming issues 522--522
William M. Kantor Finding Sylow normalizers in polynomial
time . . . . . . . . . . . . . . . . . . 523--563
David M. Mount and
Ruth Silverman Packing and covering the plane with
translates of a convex polygon . . . . . 564--580
Dennis Shasha and
Kaizhong Zhang Fast algorithms for the unit cost
editing distance between trees . . . . . 581--621
Yishay Mansour and
Leonard Schulman Sorting on a ring of processors . . . . 622--630
Hans L. Bodlaender Polynomial algorithms for graph
isomorphism and chromatic index on
partial $k$-trees . . . . . . . . . . . 631--643
Johan Håstad Tensor rank is NP-complete . . . . . . . 644--654
Anonymous Papers to appear in forthcoming issues 655--656
Anonymous Author index for volume 11 . . . . . . . 657--658
Jirí Matousek and
Robin Thomas Algorithms finding tree-decompositions
of graphs . . . . . . . . . . . . . . . 1--22
Xin He An improved algorithm for the planar
3-cut problem . . . . . . . . . . . . . 23--37
Alok Aggarwal and
Hiroshi Imai and
Naoki Katoh and
Subhash Suri Finding $k$ points with minimum diameter
and related problems . . . . . . . . . . 38--56
Siu Wing Cheng and
Ravi Janardan Efficient maintenance of the union of
intervals on a line, with applications 57--74
Subir Kumar Ghosh Computing the visibility polygon from a
convex set and related problems . . . . 75--95
T. Przytycka and
D. G. Corneil Parallel algorithms for parity graphs 96--109
Phillip Gibbons and
Richard Karp and
Vijaya Ramachandran and
Danny Soroker and
Robert Tarjan Transitive compaction in parallel via
branchings . . . . . . . . . . . . . . . 110--125
Ryan Hayward and
Colin McDiarmid Average case analysis of heap building
by repeated insertion . . . . . . . . . 126--153
Jimmy J. M. Tan A necessary and sufficient condition for
the existence of a complete stable
matching . . . . . . . . . . . . . . . . 154--178
Herbert S. Wilf Two algorithms for the sieve method . . 179--182
Peter van Emde Boas Problems . . . . . . . . . . . . . . . . 183--185
Anonymous Papers to appear in forthcoming issues 186--187
Anonymous Editorial Board . . . . . . . . . . . . ??
J. Csirik and
J. B. G. Frenk and
G. Galambos and
A. H. G. Rinnooy Kan Probabilistic analysis of algorithms for
dual bin packing problems . . . . . . . 189--203
Hagit Attiya and
Marc Snir Better computing on the anonymous ring 204--238
D. Bienstock and
Paul Seymour Monotonicity in graph searching . . . . 239--245
Young Man Kim and
Ten-Hwang Lai The complexity of congestion-1 embedding
in a hypercube . . . . . . . . . . . . . 246--280
H. Zantema Minimizing sums of addition chains . . . 281--307
Stefan Arnborg and
Jens Lagergren and
Detlef Seese Easy problems for tree-decomposable
graphs . . . . . . . . . . . . . . . . . 308--340
Vasilis Capoyleas and
Günter Rote and
Gerhard Woeginger Geometric clusterings . . . . . . . . . 341--356
Anonymous Papers to appear in forthcoming issues 357--358
Steven S. Skiena Probing convex polygons with half-planes 359--374
Lin Chen and
Yaacov Yesha Parallel recognition of the consecutive
ones property with applications . . . . 375--392
M. S. Paterson and
A. A. Razborov The set of minimal braids is
co-NP-complete . . . . . . . . . . . . . 393--408
Xin He Efficient parallel algorithms for series
parallel graphs . . . . . . . . . . . . 409--430
John Hershberger and
Subhash Suri Finding tailored partitions . . . . . . 431--463
Ming-Deh A. Huang Generalized Riemann Hypothesis and
factoring polynomials over finite fields 464--481
Ming-Deh A. Huang Factorization of polynomials over finite
fields and decomposition of primes in
algebraic number fields . . . . . . . . 482--489
Lawrence L. Larmore and
Baruch Schieber On-line dynamic programming with
applications to the prediction of RNA
secondary structure . . . . . . . . . . 490--515
Jehoshua Bruck and
Vwani P. Roychowdhury How to play bowling in parallel on the
grid . . . . . . . . . . . . . . . . . . 516--529
Anonymous Papers to appear in forthcoming issues 530--531
Micha Hofri and
Hadas Shachnai Self-organizing lists and independent
references: a statistical synergy . . . 533--555
Brigitte Vallée Gauss' algorithm revisited . . . . . . . 556--572
Yossi Matias and
Uzi Vishkin On parallel hashing and integer sorting 573--606
Marek Chrobak and
Lawrence L. Larmore On fast algorithms for two servers . . . 607--614
Giorgio Ausiello and
Giuseppe F. Italiano and
Alberto Marchetti Spaccamela and
Umberto Nanni Incremental algorithms for minimal
length paths . . . . . . . . . . . . . . 615--638
James R. Bergen and
Haim Shvaytser (Schweitzer) A probabilistic algorithm for computing
Hough transforms . . . . . . . . . . . . 639--656
Binghuan Zhu and
Wayne Goddard An algorithm for outerplanar graphs with
parameter . . . . . . . . . . . . . . . 657--662
Xiaolin Wu Optimal quantization by matrix searching 663--673
Ludek Kucera The greedy coloring is a bad
probabilistic algorithm . . . . . . . . 674--684
Amos Fiat and
Richard M. Karp and
Michael Luby and
Lyle A. McGeoch and
Daniel D. Sleator and
Neal E. Young Competitive paging algorithms . . . . . 685--699
Peter van Emde Boas Problems . . . . . . . . . . . . . . . . 700--703
Anonymous Papers to appear in forthcoming issues 704--705
Anonymous Author index for volume 12 . . . . . . . 706--707
David S. Johnson Editor's foreword . . . . . . . . . . . 1--1
Amihood Amir and
Gad M. Landau and
Uzi Vishkin Efficient pattern matching with scaling 2--32
David Eppstein and
Giuseppe F. Italiano and
Roberto Tamassia and
Robert E. Tarjan and
Jeffery Westbrook and
Moti Yung Maintenance of a minimum spanning forest
in a dynamic plane graph . . . . . . . . 33--54
Maria M. Klawe Superlinear bounds for matrix searching
problems . . . . . . . . . . . . . . . . 55--78
Carolyn Haibt Norton and
Serge A. Plotkin and
Éva Tardos Using separation algorithms in fixed
dimension . . . . . . . . . . . . . . . 79--98
Michael S. Paterson and
F. Frances Yao Optimal binary space partitions for
orthogonal objects . . . . . . . . . . . 99--113
Jòrgen Bang-Jensen and
Yannis Manoussakis and
Carsten Thomassen A polynomial algorithm for
Hamiltonian-connectedness in
semicomplete digraphs . . . . . . . . . 114--127
Leslie Ann Goldberg Efficient algorithms for listing
unlabeled graphs . . . . . . . . . . . . 128--143
Peter Avery An algorithmic proof that semiorders are
representable . . . . . . . . . . . . . 144--147
D. S. Hirschberg and
L. L. Larmore The Traveler's Problem . . . . . . . . . 148--160
Toshinobu Kashiwabara and
Sumio Masuda and
Kazuo Nakajima and
Toshio Fujisawa Generation of maximum independent sets
of a bipartite graph and maximum cliques
of a circular-arc graph . . . . . . . . 161--174
Anonymous Papers to appear in forthcoming issues 175--176
Anonymous Editorial Board . . . . . . . . . . . . ??
P. P. Chakrabarti and
S. Ghose A general best first search algorithm in
AND/OR graphs . . . . . . . . . . . . . 177--187
Noga Alon and
Amotz Bar-Noy and
Nathan Linial and
David Peleg Single round simulation on radio
networks . . . . . . . . . . . . . . . . 188--210
Robert Cypher and
Jorge L. C. Sanz Cubesort: a parallel algorithm for
sorting $N$ data items with $S$-sorters 211--234
K. V. S. Ramarao and
S. Venkatesan On finding and updating shortest paths
distributively . . . . . . . . . . . . . 235--257
P. M. Camerini and
G. Galbiati and
F. Maffioli Random pseudo-polynomial algorithms for
exact matroid problems . . . . . . . . . 258--273
Mark T. de Berg and
Svante Carlsson and
Mark H. Overmars A general approach to dominance in the
plane . . . . . . . . . . . . . . . . . 274--296
Kenneth D. Blaha Minimum bases for permutation groups:
the greedy approximation . . . . . . . . 297--306
Jirí Matousek and
Emo Welzl Good splitters for counting points in
triangles . . . . . . . . . . . . . . . 307--319
Michael Lindenbaum and
Alfred Bruckstein Parallel strategies for geometric
probing . . . . . . . . . . . . . . . . 320--349
Anonymous Papers to appear in forthcoming issues 350--351
Daniel M. Yellin Representing sets with constant time
equality testing . . . . . . . . . . . . 353--373
J. Ian Munro and
Venkatesh Raman Sorting with minimum data movement . . . 374--393
Mikhail J. Atallah and
S. Rao Kosaraju An efficient parallel algorithm for the
row minima of a totally monotone matrix 394--413
Frank Ruskey and
Carla Savage and
Terry Min Yih Wang Generating necklaces . . . . . . . . . . 414--430
Sandra Fillebrown Faster computation of Bernoulli numbers 431--445
Alberto Apostolico and
Wojciech Szpankowski Self-alignments in words and their
applications . . . . . . . . . . . . . . 446--467
F. K. Hwang and
J. F. Weng The shortest network under a given
topology . . . . . . . . . . . . . . . . 468--488
Uzi Vishkin A parallel blocking flow algorithm for
acyclic networks . . . . . . . . . . . . 489--501
David S. Johnson The NP-completeness column: an ongoing
guide . . . . . . . . . . . . . . . . . 502--524
Anonymous Papers to appear in forthcoming issues 525--526
Hugo Krawczyk How to predict congruential generators 527--545
Anat Fischer and
Itzhak Gilboa and
Moshe Shpitalni A polynomial algorithm for minimal
interval representation . . . . . . . . 546--563
Grazia Lotti Fast solution of linear systems with
polynomial coefficients over the ring of
integers . . . . . . . . . . . . . . . . 564--576
Amir Averbuch and
Nader H. Bshouty and
Michael Kaminski A classification of algorithms for
multiplying polynomials of small degree
over finite fields . . . . . . . . . . . 577--588
Keoin Li and
Kam Hoi Cheng Heuristic algorithms for on-line packing
in three dimensions . . . . . . . . . . 589--605
Hitoshi Suzuki and
Akira Ishiguro and
Takao Nishizeki Variable-priority queue and doughnut
routing . . . . . . . . . . . . . . . . 606--635
Yitzhak Birk and
Jeffrey B. Lotspiech On finding non-intersecting straightline
connections of grid points to the
boundary . . . . . . . . . . . . . . . . 636--656
Sundar Vishwanathan Randomized online graph coloring . . . . 657--669
Siu Wing Cheng and
Ravi Janardan Algorithms for ray-shooting and
intersection searching . . . . . . . . . 670--692
Jeff Chu Optimal algorithm for the nearest common
dominator problem . . . . . . . . . . . 693--697
Anonymous Papers to appear in forthcoming issues 698--699
Anonymous Author index for volume 13 . . . . . . . 700--701
H. L. Bodlaender On Linear Time Minor Tests with
Depth-First Search . . . . . . . . . . . 1--23
J. Z. Du and
J. Y. T. Leung Minimizing Mean Flow Time in Two-Machine
Open Shops and Flow Shops . . . . . . . 24--44
J. Z. Du and
J. Y. T. Leung Minimizing Mean Flow Time With Release
Time and Deadline Constraints . . . . . 45--68
P. K. Agarwal and
M. Sharir Circle Shooting in a Simple Polygon . . 69--87
R. S. Valiveti and
B. J. Oommen Self-Organizing Doubly-Linked Lists . . 88--114
P. Hell and
D. G. Kirkpatrick Algorithms for Degree Constrained Graph
Factors of Minimum Deficiency . . . . . 115--138
J. I. Doh and
K. Y. Chwa An Algorithm for Determining Visibility
of a Simple Polygon from an Internal
Line Segment . . . . . . . . . . . . . . 139--168
D. Pearson and
V. V. Vazirani Efficient Sequential and Parallel
Algorithms for Maximal Bipartite Sets 171--179
A. V. Goldberg and
S. A. Plotkin and
P. M. Vaidya Sublinear-Time Parallel Algorithms for
Matching and Related Problems . . . . . 180--213
S. Khuller and
R. Thurimella Approximation Algorithms for Graph
Augmentation . . . . . . . . . . . . . . 214--225
J. Zerovnik and
T. Pisanski Computing the Diameter in Multiple-Loop
Networks . . . . . . . . . . . . . . . . 226--243
O. H. Ibarra and
H. Wang and
T. Jiang On Efficient Parallel Algorithms for
Solving Set Recurrence Equations . . . . 244--257
K. Diks and
H. N. Djidjev and
O. Sykora and
I. Vrto Edge Separators of Planar and
Outerplanar Graphs With Applications . . 258--279
M. Karpinski and
M. Luby Approximating the Number of Zeroes of a
${\rm GF}[2]$ Polynomial . . . . . . . . 280--287
S. Bitan and
S. Zaks Optimal Linear Broadcast . . . . . . . . 288--315
Y. Afek and
M. Ricklin Sparser: a Paradigm for Running
Distributed Algorithms . . . . . . . . . 316--328
P. N. Klein Parallelism, Preprocessing, and
Reachability: a Hybrid Algorithm for
Directed Graphs . . . . . . . . . . . . 331--343
O. Berkman and
B. Schieber and
U. Vishkin Optimal Doubly Logarithmic Parallel
Algorithms Based On Finding All Nearest
Smaller Values . . . . . . . . . . . . . 344--370
P. Ragde The Parallel Simplicity of Compaction
and Chaining . . . . . . . . . . . . . . 371--380
L. Devroye and
G. Toussaint Convex Hulls for Random Lines . . . . . 381--394
C. Levcopoulos and
O. Petersson Adaptive Heapsort . . . . . . . . . . . 395--413
J. Aspnes Time- and Space-Efficient Randomized
Consensus . . . . . . . . . . . . . . . 414--431
J. Matousek Linear Optimization Queries . . . . . . 432--448
Y. Mansour and
B. Pattshamir Greedy Packet Scheduling on Shortest
Paths . . . . . . . . . . . . . . . . . 449--465
B. F. Wang and
G. H. Chen and
K. Park On the Set LCS and Set-Set LCS Problems 466--477
B. Kalyanasundaram and
K. Pruhs Online Weighted Matching . . . . . . . . 478--488
Anonymous Author Index for Volume 14 . . . . . . . 490--490
J. Csirik The Parametric Behavior of the First-Fit
Decreasing Bin Packing Algorithm . . . . 1--28
G. N. Frederickson and
D. J. Guan Nonpreemptive Ensemble Motion Planning
on a Tree . . . . . . . . . . . . . . . 29--60
C. Thomassen The Even Cycle Problem for Planar
Digraphs . . . . . . . . . . . . . . . . 61--75
R. Schaffer and
R. Sedgewick The Analysis of Heapsort . . . . . . . . 76--100
B. Poonen The Worst Case in Shellsort and Related
Algorithms . . . . . . . . . . . . . . . 101--124
D. Hartvigsen Minimum Path Bases . . . . . . . . . . . 125--142
S. T. Peng and
A. B. Stephens and
Y. Yesha Algorithms for a Core and $k$-Tree Core
of a Tree . . . . . . . . . . . . . . . 143--159
H. Bodlaender and
T. Kloks A Simple Linear Time Algorithm for
Triangulating Three-Colored Graphs . . . 160--172
D. Eppstein and
G. F. Italiano and
R. Tamassia and
R. E. Tarjan and
J. Westbrook and
M. Yung Erratum: Volume 13, Number 1 (1992), in
the article ``Maintenance of a Minimum
Spanning Forest in a Dynamic Plane
Graph,'' by David Eppstein, Giuseppe F.
Italiano, Roberto Tamassia, Robert E.
Tarjan, Jeffery Westbrook, and Moti
Yung, pages 33--54 . . . . . . . . . . . 173--173
I. Althofer A Parallel Game Tree Search Algorithm
With a Linear Speedup . . . . . . . . . 175--198
E. Bach and
J. Driscoll and
J. Shallit Factor Refinement . . . . . . . . . . . 199--222
J. Joichi and
D. Stanton An Algorithmic Involution for $p(n)$ . . 223--228
P. K. Agarwal and
M. Vankreveld and
M. Overmars Intersection Queries in Curved Objects 229--266
M. Formann and
D. Wagner and
F. Wagner Routing through a Dense Channel with
Minimum Total Wire Length . . . . . . . 267--283
X. He Parallel Algorithm for Cograph
Recognition with Applications . . . . . 284--313
P. K. Agarwal and
A. Efrat and
M. Sharir and
S. Toledo Computing a Segment Center for a Planar
Point Set . . . . . . . . . . . . . . . 314--323
Y. Koda and
F. Ruskey A Gray Code for the Ideals of a Forest
Poset . . . . . . . . . . . . . . . . . 324--340
J. M. Lucas and
D. R. Vanbaronaigien and
F. Ruskey On Rotations and the Generation of
Binary Trees . . . . . . . . . . . . . . 343--366
E. Dahlhaus and
P. Hajnal and
M. Karpinski On the Parallel Complexity of
Hamiltonian Cycle and Matching Problem
on Dense Graphs . . . . . . . . . . . . 367--384
J. Barilan and
G. Kortsarz and
D. Peleg How to Allocate Network Centers . . . . 385--415
H. Booth and
R. E. Tarjan Finding the Minimum-Cost Maximum Flow in
a Series-Parallel Network . . . . . . . 416--446
L. C. K. Hui and
C. Martel Unsuccessful Search in Self-Adjusting
Data Structures . . . . . . . . . . . . 447--481
B. Mohar Projective Planarity in Linear Time . . 482--502
Anonymous Author Index for Volume 15 . . . . . . . 504--504
U. K. Sarkar and
P. P. Chakrabarti and
S. Ghose and
S. C. Desarkar Improving Greedy Algorithms by
Lookahead-Search . . . . . . . . . . . . 1--23
L. Ronyai A Deterministic Method for Computing
Splitting Elements in Simple Algebras
over $Q$ . . . . . . . . . . . . . . . . 24--32
K. Z. Zhang and
D. Shasha and
J. T. L. Wang Approximate Tree Matching in the
Presence of Variable Length Don't Cares 33--66
R. M. Verma A General Method and a Master Theorem
for Divide-and-Conquer Recurrences with
Applications . . . . . . . . . . . . . . 67--79
N. Alon and
R. A. Duke and
H. Lefmann and
V. Rodl and
R. Yuster The Algorithmic Aspects of the
Regularity Lemma . . . . . . . . . . . . 80--109
J. Sorenson Two Fast GCD Algorithms . . . . . . . . 110--144
T. H. Ma and
J. Spinrad An $O(n^2)$ Algorithm for Undirected
Split Decomposition . . . . . . . . . . 145--160
L. Colussi Fastest Pattern Matching in Strings . . 163--189
K. Iwama and
Y. Kambayashi A Simpler Parallel Algorithm for Graph
Connectivity . . . . . . . . . . . . . . 190--217
J. P. Doignon and
J. C. Falmagne A Polynomial Time Algorithm for
Unidimensional Unfolding Representations 218--233
M. Chrobak and
L. L. Larmore Generosity Helps or an 11-Competitive
Algorithm for Three Servers . . . . . . 234--263
J. Spinrad Recognition of Circle Graphs . . . . . . 264--282
A. Ehrenfeucht and
H. N. Gabow and
R. M. Mcconnell and
S. J. Sullivan An $O(n^2)$ Divide-and-Conquer Algorithm
for the Prime Tree Decomposition of
Two-Structures and Modular Decomposition
of Graphs . . . . . . . . . . . . . . . 283--294
T. Goldberg and
U. Zwick Faster Parallel String Matching via
Larger Deterministic Samples . . . . . . 295--308
M. Filaseta and
M. L. Robinson and
F. S. Wheeler The Minimal Euclidean Norm of an
Algebraic Number Is Effectively
Computable . . . . . . . . . . . . . . . 309--333
W. Eberly Logarithmic Depth Circuits for Hermite
Interpolation . . . . . . . . . . . . . 335--360
C. Martel and
R. Subramonian On the Complexity of Certified Write-All
Algorithms . . . . . . . . . . . . . . . 361--387
T. J. Warnow Tree Compatibility and Inferring
Evolutionary History . . . . . . . . . . 388--407
D. Fernandezbaca and
G. Slutzki Parametric Problems on Graphs of Bounded
Tree-Width . . . . . . . . . . . . . . . 408--430
K. I. J. Ho and
J. Y. T. Leung and
W. D. Wei Minimizing Maximum Weighted Error for
Imprecise Computation Tasks . . . . . . 431--452
O. H. Ibarra and
Q. Zheng Some Efficient Algorithms for
Permutation Graphs . . . . . . . . . . . 453--469
E. Wanke Bounded Tree-Width and LOGCFL . . . . . 470--491
Anonymous Author Index for Volume 16 . . . . . . . 493--493
D. Kozen Foreword . . . . . . . . . . . . . . . . 1--1
J. C. Culberson and
R. A. Reckhow Covering Polygons Is Hard . . . . . . . 2--44
M. L. Fredman and
D. L. Goldsmith Three Stacks . . . . . . . . . . . . . . 45--70
S. M. Malitz Graphs with $E$ Edges Have Pagenumber
$O(\sqrt E)$ . . . . . . . . . . . . . . 71--84
S. M. Malitz Genus $g$ Graphs Have Pagenumber
$O(\sqrt g)$ . . . . . . . . . . . . . . 85--109
Y. Moses and
O. Waarts Coordinated Traversal: ($t$ + 1)-Round
Byzantine Agreement in Polynomial Time 110--156
F. T. Leighton and
B. M. Maggs and
A. G. Ranade and
S. B. Rao Randomized Routing and Sorting on
Fixed-Connection Networks . . . . . . . 157--205
F. Gavril and
V. T. Laredo and
D. Dewerra Chordless Paths, Odd Holes, and Kernels
in Graphs Without $m$-Obstructions . . . 207--221
G. Kortsarz and
D. Peleg Generating Sparse 2-Spanners . . . . . . 222--236
D. Eppstein Offline Algorithms for Dynamic Minimum
Spanning Tree Problems . . . . . . . . . 237--250
T. H. Ma and
J. P. Spinrad On the 2-Chain Subgraph Cover and
Related Problems . . . . . . . . . . . . 251--268
E. T. Kofler and
C. T. Leondes Algorithmic Modifications to the Theory
of Evidential Reasoning . . . . . . . . 269--279
S. Khuller and
U. Vishkin and
N. Young A Primal--Dual Parallel Approximation
Technique Applied to Weighted Set and
Vertex Covers . . . . . . . . . . . . . 280--289
G. N. Frederickson Editor Foreword . . . . . . . . . . . . 291--291
P. K. Agarwal and
M. Sharir and
S. Toledo Applications of Parametric Searching in
Geometric Optimization . . . . . . . . . 292--318
E. Bareli and
P. Berman and
A. Fiat and
P. Y. Yan Online Navigation in a Room . . . . . . 319--341
N. Baumgarten and
H. Jung and
K. Mehlhorn Dynamic Point Location in General
Subdivisions . . . . . . . . . . . . . . 342--380
P. Berman and
V. Ramaiyer Improved Approximations for the Steiner
Tree Problem . . . . . . . . . . . . . . 381--408
M. Furer and
B. Raghavachari Approximating the Minimum-Degree Steiner
Tree to within One of Optimal . . . . . 409--423
J. X. Hao and
J. B. Orlin A Faster Algorithm for Finding the
Minimum Cut in a Directed Graph . . . . 424--446
V. King and
S. Rao and
R. Tarjan A Faster Deterministic Maximum Flow
Algorithm . . . . . . . . . . . . . . . 447--474
M. Yannakakis On the Approximation of Maximum
Satisfiability . . . . . . . . . . . . . 475--502
Anonymous Author Index for Volume 17 . . . . . . . 504--504
P. Kelsen and
V. Ramachandran On Finding Minimal Two-Connected
Subgraphs . . . . . . . . . . . . . . . 1--49
R. Cole and
O. Zajicek An Asynchronous Parallel Algorithm for
Undirected Graph Connectivity . . . . . 50--97
B. Berger and
L. Cowen Scheduling with Concurrency-Based
Constraints . . . . . . . . . . . . . . 98--123
U. Schmid and
J. Blieberger On Nonpreemptive LCFS Scheduling with
Deadlines . . . . . . . . . . . . . . . 124--158
B. Chandra and
S. Vishwanathan Constructing Reliable Communication
Networks of Small Weight Online . . . . 159--175
A. Gupta and
N. Nishimura The Parallel Complexity of Tree
Embedding Problems . . . . . . . . . . . 176--200
M. Furer and
B. Raghavachari An Efficient Parallel Algorithm for
Finding Hamiltonian Cycles in Dense
Directed Graphs . . . . . . . . . . . . 203--220
Y. Azar and
J. Naor and
R. Rom The Competitiveness of On-Line
Assignments . . . . . . . . . . . . . . 221--237
H. L. Bodlaender and
J. R. Gilbert and
H. Hafsteinsson and
T. Kloks Approximating Treewidth, Pathwidth,
Frontsize, and Shortest Elimination Tree 238--255
M. Deberg and
M. Vankreveld and
J. Snoeyink Two-Dimensional and Three-Dimensional
Point Location in Rectangular
Subdivisions . . . . . . . . . . . . . . 256--277
D. Breslauer Dictionary-Matching on Unbounded
Alphabets: Uniform Length Dictionaries 278--295
Y. Caspi and
E. Dekel Edge Coloring Series Parallel Graphs . . 296--321
Y. Benasher and
A. Schuster The Complexity of Data Reduction on a
Reconfigurable Linear Array . . . . . . 322--357
T. H. Lai and
S. S. Wei Algorithms for Page Retrieval and
Hamiltonian Paths on Forward-Convex Line
Graphs . . . . . . . . . . . . . . . . . 358--375
V. Ramachandran Editor's Foreword . . . . . . . . . . . 377--377
K. W. Chong and
T. W. Lam Finding Connected Components in $O(\log
n \log \log n)$ Time on the EREW PRAM 378--402
J. Hershberger and
S. Suri A Pedestrian Approach to Ray Shooting:
Shoot a Ray, Take a Walk . . . . . . . . 403--431
M. L. Fredman and
D. S. Johnson and
L. A. Mcgeoch and
G. Ostheimer Data Structures for Traveling Salesmen 432--479
H. Ramesh On Traversing Layered Graphs On-Line . . 480--512
A. L. Buchsbaum and
R. E. Tarjan Confluently Persistent Deques via
Data-Structural Bootstrapping . . . . . 513--547
J. Ruppert A Delaunay Refinement Algorithm for
Quality 2-Dimensional Mesh Generation 548--585
H. N. Gabow Centroids, Representations, and
Submodular Flows . . . . . . . . . . . . 586--628
T. Hagerup Fast Deterministic Processor Allocation 629--649
Anonymous Author Index for Volume 18 . . . . . . . 651--651
P. Delatorre and
C. P. Kruskal Fast Parallel Algorithms for All-Sources
Lexicographic Search and Path-Algebra
Problems . . . . . . . . . . . . . . . . 1--24
M. Sherk Self-Adjusting $k$-ary Search Trees . . 25--44
G. N. Frederickson Using Cellular Graph Embeddings in
Solving All Pairs Shortest Paths
Problems . . . . . . . . . . . . . . . . 45--85
P. Bose and
G. Toussaint Growing a Tree from Its Branches . . . . 86--103
P. Klein and
R. Ravi A Nearly Best-Possible Approximation
Algorithm for Node-Weighted Steiner
Trees . . . . . . . . . . . . . . . . . 104--115
A. Aggarwal and
A. Barnoy and
S. Khuller and
D. Kravets and
B. Schieber Efficient Minimum Cost Matching and
Transportation Using the Quadrangle
Inequality . . . . . . . . . . . . . . . 116--143
W. L. Hsu and
J. P. Spinrad Independent Sets in Circular-Arc Graphs 145--160
S. D. Sen Fractional Cascading Revisited . . . . . 161--172
V. Chandru and
S. K. Ghosh and
A. Maheshwari and
V. T. Rajan and
S. J. Saluja $N C$-Algorithms for Minimum Link Path
and Related Problems . . . . . . . . . . 173--203
A. Blum and
J. Spencer Coloring Random and Semi-Random
$k$-Colorable Graphs . . . . . . . . . . 204--234
F. Manne and
T. Sorevik Optimal Partitioning of Sequences . . . 235--249
C. Pomerance and
J. Sorenson Counting the Integers Factorable via
Cyclotomic Methods . . . . . . . . . . . 250--265
T. Kloks and
D. Kratsch Treewidth of Chordal Bipartite Graphs 266--281
P. Gupta and
R. Janardan and
M. Smid Further Results on Generalized
Intersection Searching Problems:
Counting, Reporting, and Dynamization 282--317
A. Aggarwal and
T. Tokuyama An Improved Algorithm for the Traveler's
Problem . . . . . . . . . . . . . . . . 318--330
X. D. Zhu A Polynomial Algorithm for Homomorphisms
to Oriented Cycles . . . . . . . . . . . 333--345
S. Wu and
U. Manber and
E. Myers A Subquadratic Algorithm for Approximate
Regular Expression Matching . . . . . . 346--360
S. Rajasekaran $k$--$k$ Routing, $k$--$k$ Sorting, and
Cut-Through Routing on the Mesh . . . . 361--382
D. B. Johnson and
P. Metaxas A Parallel Algorithm for Computing
Minimum Spanning Trees . . . . . . . . . 383--401
W. F. Eddy and
M. J. Schervish How Many Comparisons Does Quicksort Use? 402--431
E. Bampis and
M. Elhaddad and
Y. Manoussakis and
M. Santha A Parallel Reduction of Hamiltonian
Cycle to Hamiltonian Path in Tournaments 432--440
K. Engel An Algorithm for the Determination of
the Variance of a Partially Ordered Set 441--448
M. C. Golumbic and
H. Kaplan and
R. Shamir Graph Sandwich Problems . . . . . . . . 449--473
A. Datta and
H. P. Lenhof and
C. Schwarz and
M. Smid Static and Dynamic Algorithms for
$k$-Point Clustering Problems . . . . . 474--503
Anonymous Author Index for Volume 19 . . . . . . . 505--505
Danny Krizanc Time-Randomness Trade-offs in Parallel
Computation . . . . . . . . . . . . . . 1--19
Jens Lagergren Efficient Parallel Algorithms for Graphs
of Bounded Tree-Width . . . . . . . . . 20--44
Jonathan F. Buss and
Paris C. Kanellakis and
Prabhakar L. Ragde and
Alex Allister Shvartsman Parallel Algorithms with Processor
Failures and Delays . . . . . . . . . . 45--86
David Cohen and
Michael L. Fredman Weighted Binary Trees for Concurrent
Searching . . . . . . . . . . . . . . . 87--112
André van Vliet On the Asymptotic Worst Case Behavior of
Harmonic Fit . . . . . . . . . . . . . . 113--136
Yair Caro and
András Sebo\Ho and
Michael Tarsi Recognizing Greedy Structures . . . . . 137--156
Jan Karel Lenstra and
Marinus Veldhorst and
Bart Veltman The Complexity of Scheduling Trees with
Communication Delays . . . . . . . . . . 157--173
Xiao Zhou and
Hitoshi Suzuki and
Takao Nishizeki A Linear Algorithm for Edge-Coloring
Series-Parallel Multigraphs . . . . . . 174--201
Anonymous Papers to Appear in Forthcoming Issues 202--202
Serge Abiteboul and
Gabriel M. Kuper and
Harry G. Mairson and
Alex A. Shvartsman and
Moshe Y. Vardi In Memoriam: Paris C. Kanellakis
(1953--1995) . . . . . . . . . . . . . . 203--204
B. Bollobás and
T. I. Fenner and
A. M. Frieze On the Best Case of Heapsort . . . . . . 205--217
Alon Itai and
Hadas Shachnai Adaptive Source Routing in High-Speed
Networks . . . . . . . . . . . . . . . . 218--243
Shreesh Jadhav and
Asish Mukhopadhyay and
Binay Bhattacharya An Optimal Algorithm for the
Intersection Radius of a Set of Convex
Polygons . . . . . . . . . . . . . . . . 244--267
Charles J. Colbourn and
Wendy J. Myrvold and
Eugene Neufeld Two Algorithms for Unranking
Arborescences . . . . . . . . . . . . . 268--281
Pallab Dasgupta and
P. P. Chakrabarti and
S. C. DeSarkar Multiobjective Heuristic Search in
AND/OR Graphs . . . . . . . . . . . . . 282--311
Alan Frieze and
Stephen Suen Analysis of Two Simple Heuristics on a
Random Instance of $k$- sat . . . . . . 312--355
Alessandro Panconesi and
Aravind Srinivasan On the Complexity of Distributed Network
Decomposition . . . . . . . . . . . . . 356--374
Volker Heun and
Ernst W. Mayr A New Efficient Algorithm for Embedding
an Arbitrary Binary Tree into Its
Optimal Hypercube . . . . . . . . . . . 375--399
David R. Karger and
Steven J. Phillips and
Eric Torng A Better Algorithm for an Ancient
Scheduling Problem . . . . . . . . . . . 400--430
Donald E. Knuth An Exact Analysis of Stable Allocation 431--442
Shietung Peng and
Win-tsung Lo Efficient Algorithms for Finding a Core
of a Tree with a Specified Length . . . 445--458
Danny Z. Chen Optimally Computing the Shortest Weakly
Visible Subedge of a Simple Polygon . . 459--478
William R. Burley Traversing Layered Graphs Using the Work
Function Algorithm . . . . . . . . . . . 479--511
Ashok Subramanian An Explanation of Splaying . . . . . . . 512--525
Kazuo Iwama and
Chuzo Iwamoto $\alpha$-connectivity: a gradually
nonparallel graph problem . . . . . . . 526--544
Ji\vrí Matousek Derandomization in Computational
Geometry . . . . . . . . . . . . . . . . 545--580
Pankaj K. Agarwal and
Sandeep Sen Selection in Monotone Matrices and
Computing $k$th Nearest Neighbors . . . 581--601
Mikkel Thorup Efficient Preprocessing of Simple Binary
Pattern Forests . . . . . . . . . . . . 602--612
Kazuo Iwama and
Eiji Miyano and
Yahiko Kambayashi Routing Problems on the Mesh of Buses 613--631
Anonymous Author Index for Volume 20 . . . . . . . 633--633
Anonymous Papers to Appear in Forthcoming Issues 633--633
Anonymous Cumulative Index for Volumes 1-20 . . . 634--660
Goos Kant Augmenting Outerplanar Graphs . . . . . 1--25
Sampath K. Kannan and
Eugene L. Lawler and
Tandy J. Warnow Determining the Evolutionary Tree Using
Experiments . . . . . . . . . . . . . . 26--50
Anna Galluccio and
Martin Loebl Cycles of Prescribed Modularity in
Planar Digraphs . . . . . . . . . . . . 51--70
Artur Czumaj Very Fast Approximation of the Matrix
Chain Product Problem . . . . . . . . . 71--79
Marco Pellegrini Repetitive Hidden Surface Removal for
Polyhedra . . . . . . . . . . . . . . . 80--101
Dusan Hvalica Best First Search Algorithm in AND/OR
Graphs with Cycles . . . . . . . . . . . 102--110
D. Eu and
E. Guévremont and
G. T. Toussaint On Envelopes of Arrangements of Lines 111--148
Ji\vrí Sgall Randomized On-line Scheduling of
Parallel Jobs . . . . . . . . . . . . . 149--175
Alan Frieze and
Mark Jerrum and
Michael Molloy and
Robert Robinson and
Nicholas Wormald Generating and Counting Hamilton Cycles
in Random Regular Graphs . . . . . . . . 176--198
Roberto Tamassia On-line Planar Graph Embedding . . . . . 201--239
Paul Tseng and
Zhi-Quan Luo On Computing the Nested Sums and Infimal
Convolutions of Convex Piecewise-Linear
Functions . . . . . . . . . . . . . . . 240--266
G. Ramalingam and
Thomas Reps An Incremental Algorithm for a
Generalization of the Shortest-Path
Problem . . . . . . . . . . . . . . . . 267--305
H. Narayanan and
Subir Roy and
Sachin Patkar Approximation Algorithms for
Min-$k$-Overlap Problems Using the
Principal Lattice of Partitions Approach 306--330
Edith Cohen Efficient Parallel Shortest-Paths in
Digraphs with a Separator Decomposition 331--357
Hans L. Bodlaender and
Ton Kloks Efficient and Constructive Algorithms
for the Pathwidth and Treewidth of
Graphs . . . . . . . . . . . . . . . . . 358--402
Dorit S. Hochbaum and
Joseph (Seffi) Naor Approximation Algorithms for Network
Design Problems on Bounded Subsets . . . 403--414
J. A. Hoogeveen Single-Machine Scheduling to Minimize a
Function of Two or Three Maximum Cost
Criteria . . . . . . . . . . . . . . . . 415--433
Samir Khuller and
Balaji Raghavachari Improved Approximation Algorithms for
Uniform Connectivity Problems . . . . . 434--450
John Hershberger and
Subhash Suri Off-Line Maintenance of Planar
Configurations . . . . . . . . . . . . . 453--475
C. J. H. McDiarmid and
R. B. Hayward Large Deviations for Quicksort . . . . . 476--507
Pankaj K. Agarwal and
Micha Sharir Ray Shooting Amidst Convex Polygons in
$2$D . . . . . . . . . . . . . . . . . . 508--519
Bruno Becker and
Paolo Giulio Franciosa and
Stephan Gschwind and
Stefano Leonardi and
Thomas Ohler and
Peter Widmayer Enclosing a Set of Objects by Two
Minimum Area Rectangles . . . . . . . . 520--541
L. Babel and
I. N. Ponomarenko and
G. Tinhofer The Isomorphism Problem For Directed
Path Graphs and For Rooted Directed Path
Graphs . . . . . . . . . . . . . . . . . 542--564
Michael Kaib and
Claus P. Schnorr The Generalized Gauss Reduction
Algorithm . . . . . . . . . . . . . . . 565--578
Bernard Chazelle and
Jirí Matousek On Linear-Time Deterministic Algorithms
for Optimization Problems in Fixed
Dimension . . . . . . . . . . . . . . . 579--597
Xiao Zhou and
Shin-ichi Nakano and
Takao Nishizeki Edge-Coloring Partial $k$-Trees . . . . 598--617
Michael L. Fredman and
Leonid Khachiyan On the Complexity of Dualization of
Monotone Disjunctive Normal Forms . . . 618--628
Mark H. Overmars and
Frank A. van der Stappen Range Searching and Point Location among
Fat Objects . . . . . . . . . . . . . . 629--656
Subir Kumar Ghosh A Note on Computing the Visibility
Polygon from a Convex Chain . . . . . . 657--662
Anonymous Papers to Appear in Forthcoming Issues 663--663
Andrew V. Goldberg An Efficient Implementation of a Scaling
Minimum-Cost Flow Algorithm . . . . . . 1--29
Edith Cohen Using Selective Path-Doubling for
Parallel Shortest-Path Computations . . 30--56
Leonidas Palios Connecting the Maximum Number of Nodes
in the Grid to the Boundary with
Nonintersecting Line Segments . . . . . 57--92
Yossi Azar and
Bala Kalyanasundaram and
Serge Plotkin and
Kirk R. Pruhs and
Orli Waarts On-Line Load Balancing of Temporary
Tasks . . . . . . . . . . . . . . . . . 93--110
Jop F. Sibeyn and
Bogdan S. Chlebus and
Michael Kaufmann Deterministic Permutation Routing on
Meshes . . . . . . . . . . . . . . . . . 111--141
Himanshu Gupta and
Rephael Wenger Constructing Piecewise Linear
Homeomorphisms of Simple Polygons . . . 142--157
Yehuda Afek and
Baruch Awerbuch and
Eli Gafni and
Yishay Mansour and
Adi Rosén and
Nir Shavit Slide --- The Key to Polynomial
End-to-End Communication . . . . . . . . 158--186
Michal Penn and
Haya Shasha-Krupnik NOTE Improved Approximation Algorithms
for Weighted 2- and 3-Vertex
Connectivity Augmentation Problems . . . 187--196
Anonymous Papers to Appear in Forthcoming Issues 197--197
Piotr Berman and
Krzysztof Diks and
Andrzej Pelc Reliable Broadcasting in Logarithmic
Time with Byzantine Link Failures . . . 199--211
David Fernández-Baca and
Giora Slutzki Optimal Parametric Search on Graphs of
Bounded Tree-Width . . . . . . . . . . . 212--240
Philip N. Klein and
Serge A. Plotkin and
Satish Rao and
Éva Tardos Approximation Algorithms for Steiner and
Directed Multicuts . . . . . . . . . . . 241--269
Pilar de la Torre and
David T. Kao A Uniform Approach to the Analysis of
Trie Structures That Store
Prefixing-Keys . . . . . . . . . . . . . 270--295
Paolo Ferragina Dynamic Text Indexing under String
Updates . . . . . . . . . . . . . . . . 296--328
Christine Rüb On the Average Running Time of Odd-Even
Merge Sort . . . . . . . . . . . . . . . 329--346
John H. Reif and
Stephen R. Tate On Dynamic Algorithms for Algebraic
Problems . . . . . . . . . . . . . . . . 347--371
James Jianghai Fu Directed Graph Pattern Matching and
Topological Embedding . . . . . . . . . 372--391
Anonymous Papers to Appear in Forthcoming Issues 392--392
Anonymous Author Index for Volume 22 . . . . . . . 393--393
Vijaya Ramachandran Parallel Algorithms for Reducible Flow
Graphs . . . . . . . . . . . . . . . . . 1--31
Evangelos Kranakis and
Danny Krizanc Distributed Computing on Anonymous
Hypercube Networks . . . . . . . . . . . 32--50
Michael T. Goodrich and
Roberto Tamassia Dynamic Ray Shooting and Shortest Paths
in Planar Subdivisions via Balanced
Geodesic Triangulations . . . . . . . . 51--73
Artur Czumaj and
Leszek Gasieniec and
Marek Piotrów and
Wojciech Rytter Sequential and Parallel Approximation of
Shortest Superstrings . . . . . . . . . 74--100
Ishai Ben Aroya and
Ilan Newman and
Assaf Schuster Randomized Single-Target Hot-Potato
Routing . . . . . . . . . . . . . . . . 101--120
Karsten Weihe Edge-Disjoint $(s, t)$-Paths in
Undirected Planar Graphs in Linear Time 121--138
Mikkel Thorup Parallel Shortcutting of Rooted Trees 139--159
Ramakrishna Thurimella Sub-linear Distributed Algorithms for
Sparse Certificates and Biconnected
Components . . . . . . . . . . . . . . . 160--179
Juan A. Garay and
Inder S. Gopal and
Shay Kutten and
Yishay Mansour and
Moti Yung Efficient On-Line Call Control
Algorithms . . . . . . . . . . . . . . . 180--194
Boris Pittel and
Robert S. Weishaar On-Line Coloring of Sparse Random Graphs
and Random Trees . . . . . . . . . . . . 195--205
Anonymous Papers to Appear in Forthcoming Issues 206--206
Martin Loebl and
Jaroslav Nesetril Linearity and Unprovability of Set Union
Problem Strategies . . . . . . . . . . . 207--220
C. Greg Plaxton and
Torsten Suel Lower Bounds for Shellsort . . . . . . . 221--240
Yair Bartal and
Adi Rosén The Distributed $k$-Server Problem --- a
Competitive Distributed Translator for
$k$-Server Algorithms . . . . . . . . . 241--264
Magnus M. Halldórsson Parallel and On-Line Graph Coloring . . 265--280
Akiyoshi Shioura and
Takeaki Uno A Linear Time Algorithm for Finding a
$k$-Tree Core . . . . . . . . . . . . . 281--290
Lisa Higham and
David Kirkpatrick and
Karl Abrahamson and
Andrew Adler Optimal Algorithms for Probabilistic
Solitude Detection on Anonymous Rings 291--328
Biing-Feng Wang Tighter Bounds on the Solution of a
Divide-and-Conquer Maximin Recurrence 329--344
Gunnar Brinkmann and
Andreas W. M. Dress A Constructive Enumeration of Fullerenes 345--358
Xiao Zhou and
Hitoshi Suzuki and
Takao Nishizeki An $N C$ Parallel Algorithm for
Edge-Coloring Series-Parallel
Multigraphs . . . . . . . . . . . . . . 359--374
David Eppstein Minimum Range Balanced Cuts via Dynamic
Subset Sums . . . . . . . . . . . . . . 375--385
Phillip G. Bradford and
Rudolf Fleischer and
Michiel Smid More Efficient Parallel Totally Monotone
Matrix Searching . . . . . . . . . . . . 386--400
Samir Khuller Problems . . . . . . . . . . . . . . . . 401--403
Anonymous Papers to Appear in Forthcoming Issues 404--404
Anonymous Author Index for Volume 23 . . . . . . . 405--405
Shlomo Moran and
Gadi Taubenfeld A Lower Bound on Wait-Free Counting . . 1--19
S. Haldar An `All Pairs Shortest Paths'
Distributed Algorithm Using $2 n^2$
Messages . . . . . . . . . . . . . . . . 20--36
Greg N. Frederickson A Data Structure for Dynamically
Maintaining Rooted Trees . . . . . . . . 37--65
Susanne E. Hambrusch and
Hung-Yi Tu Edge Weight Reduction Problems in
Directed Acyclic Graphs . . . . . . . . 66--93
Hans L. Bodlaender and
Joost Engelfriet Domino Treewidth . . . . . . . . . . . . 94--123
Marek Chrobak and
Lawrence L. Larmore and
Nick Reingold and
Jeffery Westbrook Page Migration Algorithms Using Work
Functions . . . . . . . . . . . . . . . 124--157
Shimon Even and
Ami Litman and
Peter Winkler Computing with Snakes in Directed
Networks of Automata . . . . . . . . . . 158--170
Andrei Z. Broder and
Ernst W. Mayr Counting Minimum Weight Spanning Trees 171--176
David Eppstein and
Daniel S. Hirschberg Choosing Subsets with Maximum Weighted
Average . . . . . . . . . . . . . . . . 177--193
Monika Rauch Henzinger A Static 2-Approximation Algorithm for
Vertex Connectivity and Incremental
Approximation Algorithms for Edge and
Vertex Connectivity . . . . . . . . . . 194--220
Anonymous Papers to Appear in Forthcoming Issues 221--221
Raffaele Giancarlo and
Roberto Grossi Multi-Dimensional Pattern Matching with
Dimensional Wildcards: Data Structures
and Optimal On-Line Search Algorithms 223--265
Nili Guttmann-Beck and
Refael Hassin Approximation Algorithms for Min-Max
Tree Partition . . . . . . . . . . . . . 266--286
J. Andrew Fingerhut and
Subhash Suri and
Jonathan S. Turner Designing Least-Cost Nonblocking
Broadband Networks . . . . . . . . . . . 287--309
Sándor P. Fekete and
Samir Khuller and
Monika Klemmstein and
Balaji Raghavachari and
Neal Young A Network-Flow Technique for Finding
Low-Weight Bounded-Degree Spanning Trees 310--324
Amihood Amir and
Alberto Apostolico and
Moshe Lewenstein Inverse Pattern Matching . . . . . . . . 325--339
Dany Breslauer and
Tao Jiang and
Zhigen Jiang Rotations of Periodic Strings and Short
Superstrings . . . . . . . . . . . . . . 340--353
Amihood Amir and
Gary Benson and
Martin Farach Optimal Two-Dimensional Compressed
Matching . . . . . . . . . . . . . . . . 354--379
R. Balasubramanian and
Venkatesh Raman and
G. Srinivasaragavan Finding Scores in Tournaments . . . . . 380--394
O. Dubois and
Y. Boufkhad A General Upper Bound for the
Satisfiability Threshold of Random
$r$-SAT Formulae . . . . . . . . . . . . 395--420
Anonymous Papers to Appear in Forthcoming Issues 421--421
Anonymous Author Index for Volume 24 . . . . . . . 422--422
Bonnie Berger and
Peter W. Shor Tight Bounds for the Maximum Acyclic
Subgraph Problem . . . . . . . . . . . . 1--18
Martin Dietzfelbinger and
Torben Hagerup and
Jyrki Katajainen and
Martti Penttonen A Reliable Randomized Algorithm for the
Closest-Pair Problem . . . . . . . . . . 19--51
Michel Habib and
Lhouari Nourine and
George Steiner Gray Codes for the Ideals of Interval
Orders . . . . . . . . . . . . . . . . . 52--66
Mohammad H. Heydari and
I. Hal Sudborough On the Diameter of the Pancake Network 67--94
Yehuda Afek and
Gideon Stupp Optimal Time-Space Tradeoff for Shared
Memory Leader Election . . . . . . . . . 95--117
Michael Krivelevich Approximate Set Covering in Uniform
Hypergraphs . . . . . . . . . . . . . . 118--143
M. Barbeau and
F. Kabanza and
R. St-Denis An Efficient Algorithm for Controller
Synthesis under Full Observation . . . . 144--161
Noga Alon and
Dmitry N. Kozlov Coins with Arbitrary Weights . . . . . . 162--176
Binay K. Bhattacharya and
Sandeep Sen On a Simple, Practical, Optimal,
Output-Sensitive Randomized Planar
Convex Hull Algorithm . . . . . . . . . 177--193
Andrew C. Yao and
Frances F. Yao Dictionary Look-Up with One Error . . . 194--202
Anonymous Papers to Appear in Forthcoming Issues 203--203
Philip N. Klein and
Sairam Subramanian A Randomized Parallel Algorithm for
Single-Source Shortest Paths . . . . . . 205--220
D. E. G. Hare Computing the Principal Branch of
log-Gamma . . . . . . . . . . . . . . . 221--236
Petr Slavík A Tight Analysis of the Greedy Algorithm
for Set Cover . . . . . . . . . . . . . 237--254
Lusheng Wang and
Dan Gusfield Improved Approximation Algorithms for
Tree Alignment . . . . . . . . . . . . . 255--273
József Békési and
Gábor Galambos and
Ulrich Pferschy and
Gerhard J. Woeginger Greedy Algorithms for On-Line Data
Compression . . . . . . . . . . . . . . 274--289
Yossi Azar and
Leah Epstein On Two Dimensional Packing . . . . . . . 290--310
Tomasz Luczak and
Edyta Szyma\'nska A Parallel Randomized Algorithm for
Finding a Maximal Independent Set in a
Linear Hypergraph . . . . . . . . . . . 311--320
James Korsh and
Seymour Lipschutz Generating Multiset Permutations in
Constant Time . . . . . . . . . . . . . 321--335
Binay K. Bhattacharya and
Damon Kaller An ${O}(m + n \log n)$ Algorithm for the
Maximum-Clique Problem in Circular-Arc
Graphs . . . . . . . . . . . . . . . . . 336--358
Anonymous Papers to Appear in Forthcoming Issues 359--359
Anonymous Author Index for Volume 25 . . . . . . . 360--360
Philip D. MacKenzie and
Quentin F. Stout Ultrafast Expected Time Parallel
Algorithms . . . . . . . . . . . . . . . 1--33
Sivaprakasam Sunder and
Xin He Scheduling Interval Ordered Tasks in
Parallel . . . . . . . . . . . . . . . . 34--47
Harold N. Gabow Algorithms for Graphic Polymatroids and
Parametric $s$-Sets . . . . . . . . . . 48--86
Vincenzo Auletta and
Domenico Parente and
Giuseppe Persiano Placing resources on a growing line . . 87--100
E. S. Elmallah and
L. K. Stewart Polygon Graph Recognition . . . . . . . 101--140
Sameet Agarwal and
Anne Condon On Approximation Algorithms for
Hierarchical MAX-SAT . . . . . . . . . . 141--165
Zhi-Zhong Chen Efficient Approximation Schemes for
Maximization Problems on $K_{3,3}$-free
or $K_5$-free Graphs . . . . . . . . . . 166--187
Leslie Ann Goldberg and
Paul W. Goldberg and
Cynthia A. Phillips and
Gregory B. Sorkin Constructing Computer Virus Phylogenies 188--208
Anonymous Papers to Appear in Forthcoming Issues ??
Claudio Mirolo Convex Minimization on a Grid and
Applications . . . . . . . . . . . . . . 209--237
Harry B. Hunt III and
Madhav V. Marathe and
Venkatesh Radhakrishnan and
S. S. Ravi and
Daniel J. Rosenkrantz and
Richard E. Stearns NC-Approximation Schemes for NP- and
PSPACE-Hard Problems for Geometric
Graphs . . . . . . . . . . . . . . . . . 238--274
Matthew B. Squire Generating the Acyclic Orientations of a
Graph . . . . . . . . . . . . . . . . . 275--290
Anonymous A Fast and Simple Algorithm for
Identifying 2-Monotonic Positive Boolean
Functions . . . . . . . . . . . . . . . 291--305
Brendan D. McKay Isomorph-Free Exhaustive Generation . . 306--324
Anonymous Interval Routing on $k$-Trees . . . . . 325--369
Weimin Chen More Efficient Algorithm for Ordered
Tree Inclusion . . . . . . . . . . . . . 370--385
James Aspnes and
William Hurwood Spreading Rumors Rapidly Despite an
Adversary . . . . . . . . . . . . . . . 386--411
Anonymous Papers to Appear in Forthcoming Issues 413--413
Anonymous Author Index for Volume 26 . . . . . . . 414--414
Cyril Gavoille and
Eric Guévremont Worst Case Bounds for Shortest Path
Interval Routing . . . . . . . . . . . . 1--25
Anna Galluccio and
Martin Loebl Even Directed Cycles in ${H}$-Free
Digraphs . . . . . . . . . . . . . . . . 26--41
Avner Dor The Greedy Search Algorithm on Binary
Vectors . . . . . . . . . . . . . . . . 42--60
Rajeev Motwani Realization of Matrices and Directed
Graphs . . . . . . . . . . . . . . . . . 61--74
Susanne Albers and
Hisashi Koga New On-Line Algorithms for the Page
Replication Problem . . . . . . . . . . 75--96
D. J. Hebert Cyclic Interlaced Quadtree Algorithms
for Quincunx Multiresolution . . . . . . 97--128
Daniel M. Gordon A Survey of Fast Exponentiation Methods 129--146
Timothy M. Chan Deterministic Algorithms for 2-d Convex
Programming and 3-d Online Linear
Programming . . . . . . . . . . . . . . 147--166
Anonymous Papers to Appear in Forthcoming Issues 167--167
Éva Tardos Editor's Foreword . . . . . . . . . . . 169--169
James Gary Propp and
David Bruce Wilson How to Get a Perfectly Random Sample
from a Generic Markov Chain and Generate
a Random Spanning Tree of a Directed
Graph . . . . . . . . . . . . . . . . . 170--217
Claire Kenyon and
Yuval Rabani and
Alistair Sinclair Biased Random Walks, Lyapunov Functions,
and Stochastic Analysis of Best Fit Bin
Packing . . . . . . . . . . . . . . . . 218--235
Anil Kamath and
Omri Palmon and
Serge Plotkin Routing and Admission Control in General
Topology Networks with Poisson Arrivals 236--258
Rina Panigrahy and
Sundar Vishwanathan An $O(\log* n)$ Approximation Algorithm
for the Asymmetric $p$-Center Problem 259--268
Gruia Calinescu and
Cristina G. Fernandes and
Ulrich Finkler and
Howard Karloff A Better Approximation Algorithm for
Finding Planar Subgraphs . . . . . . . . 269--302
Christos Levcopoulos and
Drago Krznaric Quasi-Greedy Triangulations
Approximating the Minimum Weight
Triangulation . . . . . . . . . . . . . 303--338
Robert Lupton and
F. Miller Maley and
Neal Young Data Collection for the Sloan Digital
Sky Survey --- a Network-Flow Heuristic 339--356
Anonymous Papers to Appear in Forthcoming Issues 357--357
Anonymous Author Index for Volume 27 . . . . . . . 358--358
Lawrence L. Larmore and
Teresa M. Przytycka The Optimal Alphabetic Tree Problem
Revisited . . . . . . . . . . . . . . . 1--20
Yanjun Zhang The Variance of Two Game Tree Algorithms 21--39
Shay Kutten and
David Peleg Fast Distributed Construction of Small
$k$-Dominating Sets and Applications . . 40--66
Baruch Awerbuch and
Yair Bartal and
Amos Fiat Distributed Paging for General Networks 67--104
Cristina G. Fernandes A Better Approximation Ratio for the
Minimum Size $k$-Edge-Connected Spanning
Subgraph Problem . . . . . . . . . . . . 105--124
Stavros G. Kolliopoulos and
Clifford Stein Finding Real-Valued Single-Source
Shortest Paths in $o(n^3)$ Expected Time 125--141
Madhav V. Marathe and
R. Ravi and
Ravi Sundaram and
S. S. Ravi and
Daniel J. Rosenkrantz and
Harry B. Hunt III Bicriteria Network Design Problems . . . 142--171
Dominique Foata and
Guo-Niu Han Transformations on Words . . . . . . . . 172--191
Samir Khuller Problems . . . . . . . . . . . . . . . . 192--195
Anonymous Papers to Appear in Forthcoming Issues 196--196
Omer Berkman and
Yossi Matias and
Prabhakar Ragde Triply-Logarithmic Parallel Upper and
Lower Bounds for Minimum and Range
Minima over Small Domains . . . . . . . 197--215
Tung-Yang Ho and
Ting-Yi Sung and
Lih-Hsing Hsu and
Chang-Hsiung Tsai and
Jeng-Yan Hwang The Recognition of Double Euler Trails
in Series-Parallel Networks . . . . . . 216--257
Jing-Chao Chen Quadripartite Sort . . . . . . . . . . . 258--271
T. Kloks and
D. Kratsch and
C. K. Wong Minimum Fill-in on Circle and
Circular-Arc Graphs . . . . . . . . . . 272--289
Hillel Gazit and
John H. Reif A Randomized Parallel Algorithm for
Planar Graph Isomorphism . . . . . . . . 290--314
Pinaki Mitra and
Subhas C. Nandy Efficient Computation of Rectilinear
Geodesic Voronoi Neighbor in the
Presence of Obstacles . . . . . . . . . 315--338
Amotz Bar-Noy and
Guy Kortsarz Minimum Color Sum of Bipartite Graphs 339--365
Anonymous Papers to Appear in Forthcoming Issues 366--366
Anonymous Author Index for Volume 28 . . . . . . . 367--367
Al Borchers and
Ding-Zhu Du and
Biao Gao and
Pengjun Wan The $k$-Steiner Ratio in the Rectilinear
Plane . . . . . . . . . . . . . . . . . 1--17
Dany Breslauer and
Livio Colussi and
Laura Toniolo On the Comparison Complexity of the
String Prefix-Matching Problem . . . . . 18--67
Sanguthevar Rajasekaran Selection on Mesh Connected Computers
with Fixed and Reconfigurable Buses . . 68--81
Srinivasa R. Arikati and
Shiva Chaudhuri and
Christos D. Zaroliagis All-Pairs Min-Cut in Sparse Networks . . 82--110
Paul E. Kearney and
Derek G. Corneil Tree Powers . . . . . . . . . . . . . . 111--131
Hsueh-I Lu and
R. Ravi Approximating Maximum Leaf Spanning
Trees in Almost Linear Time . . . . . . 132--141
Ming-Yang Kao and
Yuan Ma and
Michael Sipser and
Yiqun Yin Optimal Constructions of Hybrid
Algorithms . . . . . . . . . . . . . . . 142--164
Timothy R. Walsh Generation of Well-Formed Parenthesis
Strings in Constant Worst-Case Time . . 165--173
Dorit S. Hochbaum Approximating Clique and Biclique
Problems . . . . . . . . . . . . . . . . 174--200
Anonymous Papers to Appear in Forthcoming Issues 201--201
Kenneth L. Clarkson SODA '95 Papers . . . . . . . . . . . . 203--203
Baruch Schieber Computing a Minimum Weight $k$-Link Path
in Graphs with the Concave Monge
Property . . . . . . . . . . . . . . . . 204--222
Sampath Kannan and
Todd Proebsting Register Allocation in Structured
Programs . . . . . . . . . . . . . . . . 223--237
L. Paul Chew and
Klara Kedem and
Micha Sharir and
Boaz Tagansky and
Emo Welzl Voronoi Diagrams of Lines in 3-Space
Under Polyhedral Convex Distance
Functions . . . . . . . . . . . . . . . 238--255
Arne Andersson and
Ola Petersson Approximate Indexed Lists . . . . . . . 256--276
George S. Lueker Average-Case Analysis of Off-Line and
On-Line Knapsack Problems . . . . . . . 277--305
Miklos Ajtai and
James Aspnes and
Moni Naor and
Yuval Rabani and
Leonard J. Schulman and
Orli Waarts Fairness in Scheduling . . . . . . . . . 306--357
William Aiello and
S. Raj Rajagopalan and
Ramarathnam Venkatesan Design of Practical and Provably Good
Random Number Generators . . . . . . . . 358--389
Nabil Kahale and
Tom Leighton Greedy Dynamic Routing on Arrays . . . . 390--410
Anonymous Author Index for Volume 29 . . . . . . . 412--412
Arne Andersson General Balanced Trees . . . . . . . . . 1--18
Hanmao Shi and
Thomas H. Spencer Time-Work Tradeoffs of the Single-Source
Shortest Paths Problem . . . . . . . . . 19--32
Paul F. Dietz and
Rajeev Raman Small-Rank Selection in Parallel, with
Applications to Heap Construction . . . 33--51
Shang-Hua Teng Low Energy and Mutually Distant Sampling 52--67
Yehuda Afek and
Eytan Weisberger The Instancy of Snapshots and Commuting
Objects . . . . . . . . . . . . . . . . 68--105
Yehuda Afek and
Yishay Mansour and
Zvi Ostfeld Convergence Complexity of Optimistic
Rate-Based Flow-Control Algorithms . . . 106--143
Shay Kutten and
David Peleg Fault-Local Distributed Mending . . . . 144--165
Andreas Brandstädt and
Victor Chepoi and
Feodor Dragan Distance Approximating Trees for Chordal
and Dually Chordal Graphs . . . . . . . 166--184
Javier Yáñez and
Javier Montero A Poset Dimension Algorithm . . . . . . 185--208
Anonymous Papers to Appear in Forthcoming Issues 209--209
Edith Cohen and
David D. Lewis Approximating Matrix Multiplication for
Pattern Recognition Tasks . . . . . . . 211--252
Hiroshi Nagamochi and
Toshihide Ibaraki Augmenting Edge-Connectivity over the
Entire Range in $\tilde{O}(n m)$ Time 253--301
Nina Amenta and
Marshall Bern and
David Eppstein Optimal Point Placement for Mesh
Smoothing . . . . . . . . . . . . . . . 302--322
Fabián A. Chudak and
David B. Shmoys Approximation Algorithms for
Precedence-Constrained Scheduling
Problems on Parallel Machines that Run
at Different Speeds . . . . . . . . . . 323--343
Heather D. Booth and
Rajeev Govindan and
Michael A. Langston and
Siddharthan Ramachandramurthi Fast Algorithms for ${K}$ $_4$ Immersion
Testing . . . . . . . . . . . . . . . . 344--378
Shlomi Dolev and
Evangelos Kranakis and
Danny Krizanc Baked-Potato Routing . . . . . . . . . . 379--399
Aviv Lustig and
Oded Shmueli Acyclic Hypergraph Projections . . . . . 400--422
Wei-Mei Chen and
Hsien-Kuei Hwang and
Gen-Huey Chen The Cost Distribution of
Queue-Mergesort, Optimal Mergesorts, and
Power-of-$2$ Rules . . . . . . . . . . . 423--448
Samir Khuller and
Pankaj K. Agarwal and
Joseph O'Rourke Open Problems Presented at SCG'98 . . . 449--453
Anonymous Papers to Appear in Forthcoming Issues 454--454
Anonymous Author Index For Volume 30 . . . . . . . 455--455
Anonymous Foreword . . . . . . . . . . . . . . . . ??
Julien Basch and
Leonidas J. Guibas and
John Hershberger Data Structures for Mobile Data . . . . 1--28
Gary L. Miller and
Dafna Talmor and
Shang-Hua Teng Optimal Coarsening of Unstructured
Meshes . . . . . . . . . . . . . . . . . 29--65
Anthony LaMarca and
Richard E. Ladner The Influence of Caches on the
Performance of Sorting . . . . . . . . . 66--104
Friedhelm Meyer auf der Heide and
Berthold Vöcking Shortest-Path Routing in Arbitrary
Networks . . . . . . . . . . . . . . . . 105--131
William M. Kantor and
Eugene M. Luks and
Peter D. Mark Sylow Subgroups in Parallel . . . . . . 132--195
U. Faigle and
W. Kern and
W. M. Nawijn A Greedy On-Line Algorithm for the
$k$-Track Assignment Problem . . . . . . 196--210
Toshihiro Fujito Approximating Node-Deletion Problems for
Matroidal Properties . . . . . . . . . . 211--227
Sudipto Guha and
Samir Khuller Greedy Strikes Back: Improved Facility
Location Algorithms . . . . . . . . . . 228--248
Cristina Bazgan and
Miklos Santha and
Zsolt Tuza On the approximation of finding
a(nother) Hamiltonian cycle in cubic
Hamiltonian graphs . . . . . . . . . . . 249--268
Anonymous Papers to Appear in Forthcoming Issues 269--269
Edward A. Bender and
E. Rodney Canfield An Approximate Probabilistic Model for
Structured Gaussian Elimination . . . . 271--290
Paolo Ferragina and
Roberto Grossi Improved Dynamic Text Indexing . . . . . 291--319
Michael Saks and
Fotios Zaharoglou Optimal Space Distributed
Order-Preserving Lists . . . . . . . . . 320--334
Meena Mahajan and
Venkatesh Raman Parameterizing above Guaranteed Values:
MaxSat and MaxCut . . . . . . . . . . . 335--354
Anonymous Papers to Appear in Forthcoming Issues 355--355
Anonymous Author Index For Volume 31 . . . . . . . 356--356
Nader H. Bshouty Lower Bounds for the Complexity of
Functions in a Realistic RAM Model . . . 1--20
Vincenzo Auletta and
Yefim Dinitz and
Zeev Nutov and
Domenico Parente A $2$-Approximation Algorithm for
Finding an Optimum $3$-Vertex-Connected
Spanning Subgraph . . . . . . . . . . . 21--30
Yefim Dinitz and
Zeev Nutov A $3$-Approximation Algorithm for
Finding Optimum $4,5$-Vertex-Connected
Spanning Subgraphs . . . . . . . . . . . 31--40
Ton Kloks and
Dieter Kratsch and
Haiko Müller Approximating the Bandwidth for
Asteroidal Triple-Free Graphs . . . . . 41--57
Samir Khuller and
Manfred Göbel and
Jochen Walter Bases for Polynomial Invariants of
Conjugates of Permutation Groups . . . . 58--61
Anonymous ERRATUM . . . . . . . . . . . . . . . . 62--62
Anonymous Papers to Appear in Forthcoming Issues 63--63
Paola Bonizzoni and
Gianluca Della Vedova An Algorithm for the Modular
Decomposition of Hypergraphs . . . . . . 65--86
J. Scott Provan and
Roger C. Burk Two-Connected Augmentation Problems in
Planar Graphs . . . . . . . . . . . . . 87--107
Joseph Gil and
Alon Itai How to Pack Trees . . . . . . . . . . . 108--132
Nils Klarlund An $n \log n$ Algorithm for Online BDD
Refinement . . . . . . . . . . . . . . . 133--154
Ming Li and
Louxin Zhang Twist-Rotation Transformations of Binary
Trees and Arithmetic Expressions . . . . 155--166
Hans L. Bodlaender and
Dimitrios M. Thilikos Graphs with Branchwidth at Most Three 167--194
Ruy Luiz Milidiú and
Eduardo Sany Laber and
Artur Alves Pessoa Bounding the Compression Loss of the FGK
Algorithm . . . . . . . . . . . . . . . 195--211
David Pisinger Linear Time Algorithms for Knapsack
Problems with Bounded Weights . . . . . 1--14
Joseph Cheriyan and
Ramakrishna Thurimella Fast Algorithms for $k$-Shredders and
$k$-Node Connectivity Augmentation . . . 15--50
Lisa Fleischer Building Chain and Cactus
Representations of All Minimum Cuts from
Hao--Orlin in the Same Asymptotic Run
Time . . . . . . . . . . . . . . . . . . 51--72
Moses Charikar and
Chandra Chekuri and
To-yat Cheung and
Zuo Dai and
Ashish Goel and
Sudipto Guha and
Ming Li Approximation Algorithms for Directed
Steiner Problems . . . . . . . . . . . . 73--91
S. O. Krumke and
M. V. Marathe and
H. Noltemeier and
R. Ravi and
S. S. Ravi and
R. Sundaram and
H.-C Wirth Improving Minimum Cost Spanning Trees by
Upgrading Nodes . . . . . . . . . . . . 92--111
C. R. Subramanian Minimum Coloring $k$-Colorable Graphs in
Polynomial Average Time . . . . . . . . 112--123
Anders Yeo A Polynomial Time Algorithm for Finding
a Cycle Covering a Given Set of Vertices
in a Semicomplete Multipartite Digraph 124--139
Mario A. Lopez and
Shlomo Reisner Algorithms for Polyhedral Approximation
of Multidimensional Ellipsoids . . . . . 140--165
Alan M. Frieze and
Michael Molloy Splitting an Expander Graph . . . . . . 166--172
Noga Alon and
Benny Sudakov On Two Segmentation Problems . . . . . . 173--184
Anonymous Papers to Appear in Forthcoming Issues 185--185
Paul Pritchard On Computing the Subset Graph of a
Collection of Sets . . . . . . . . . . . 187--203
Ming-Deh A. Huang and
Ashwin J. Rao Interpolation of Sparse Multivariate
Polynomials over Large Finite Fields
with Applications . . . . . . . . . . . 204--228
Mikkel Thorup Decremental Dynamic Connectivity . . . . 229--243
Greg N. Frederickson and
Roberto Solis-Oba Increasing the Weight of Minimum
Spanning Trees . . . . . . . . . . . . . 244--266
Ron Shamir and
Dekel Tsur Faster Subtree Isomorphism . . . . . . . 267--280
Petrisor Panaite and
Andrzej Pelc Exploring Unknown Undirected Graphs . . 281--295
Dimitris Bertsimas and
David Gamarnik Asymptotically Optimal Algorithms for
Job Shop Scheduling and Packet Routing 296--318
Anonymous Papers to Appear in Forthcoming Issues 319--319
Anonymous Author Index For Volume 33 . . . . . . . 320--320
S. Muthukrishnan Simple Optimal Parallel Multiple Pattern
Matching . . . . . . . . . . . . . . . . 1--13
F. Höfting and
E. Wanke Polynomial-Time Analysis of Toroidal
Periodic Graphs . . . . . . . . . . . . 14--39
Farhad Shahrokhi and
Weiping Shi On Crossing Sets, Disjoint Sets, and
Pagenumber . . . . . . . . . . . . . . . 40--53
Klaus Jansen Approximation Results for the Optimum
Cost Chromatic Partition Problem . . . . 54--89
Biing-Feng Wang Efficient Parallel Algorithms for
Optimally Locating a Path and a Tree of
a Specified Length in a Weighted Tree
Network . . . . . . . . . . . . . . . . 90--108
Hagit Attiya Efficient and Robust Sharing of Memory
in Message-Passing Systems . . . . . . . 109--127
Pascal Berthomé and
Torben Hagerup and
Ilan Newman and
Assaf Schuster Self-Simulation for the Passive Optical
Star . . . . . . . . . . . . . . . . . . 128--147
Nicola Galli Average Costs of a Graph Exploration:
Upper and Lower Bounds . . . . . . . . . 148--176
Ravindra K. Ahuja and
James B. Orlin A Faster Algorithm for the Inverse
Spanning Tree Problem . . . . . . . . . 177--193
Tao Jiang and
Paul Kearney and
Ming Li Some Open Problems in Computational
Molecular Biology . . . . . . . . . . . 194--201
Anonymous Papers to Appear in Forthcoming Issues 202--202
Yuichi Asahiro and
Kazuo Iwama and
Hisao Tamaki and
Takeshi Tokuyama Greedily Finding a Dense Subgraph . . . 203--221
Monika R. Henzinger and
Satish Rao and
Harold N. Gabow Computing Vertex Connectivity: New
Bounds from Old Techniques . . . . . . . 222--250
Daniele Frigioni and
Alberto Marchetti-Spaccamela and
Umberto Nanni Fully Dynamic Algorithms for Maintaining
Shortest Paths Trees . . . . . . . . . . 251--281
Marek Chrobak and
John Noga Competitive Algorithms for Relaxed List
Update and Multilevel Caching . . . . . 282--308
James F. Korsh and
Paul LaFollette Multiset Permutations and Loopless
Generation of Ordered Trees with
Specified Degree Sequence . . . . . . . 309--336
Wun-Tat Chan and
Francis Y. L. Chin Efficient Algorithms for Finding the
Maximum Number of Disjoint Paths in
Grids . . . . . . . . . . . . . . . . . 337--369
Sally A. Goldman and
Jyoti Parwatikar and
Subhash Suri Online Scheduling with Hard Deadlines 370--389
Ajai Kapoor and
Romeo Rizzi Edge-Coloring Bipartite Graphs . . . . . 390--396
Anonymous Papers to Appear in Forthcoming Issues 397--397
Anonymous Author Index For Volume 34 . . . . . . . 398--398
Jeffery Westbrook Load Balancing for Response Time . . . . 1--16
Martin Dyer and
Catherine Greenhill On Markov Chains for Independent Sets 17--49
Sun-yuan Hsieh and
Chin-Wen Ho and
Tsan-sheng Hsu and
Ming-Tat Ko and
Gen-Huey Chen A Faster Implementation of a Parallel
Tree Contraction Scheme and Its
Application on Distance-Hereditary
Graphs . . . . . . . . . . . . . . . . . 50--81
Amihood Amir and
Moshe Lewenstein and
Noa Lewenstein Pattern Matching in Hypertext . . . . . 82--99
Dominique Roelants van Baronaigien A Loopless Gray-Code Algorithm for
Listing $k$-ary Trees . . . . . . . . . 100--107
Piotr Berman and
Moses Charikar and
Marek Karpinski On-Line Load Balancing for Related
Machines . . . . . . . . . . . . . . . . 108--121
Gilles Villard Processor Efficient Parallel Solution of
Linear Systems of Equations . . . . . . 122--126
Anonymous Papers to Appear in Forthcoming Issues 127--127
Norbert Blum Speeding Up Dynamic Programming without
Omitting any Optimal Solution and Some
Applications in Molecular Biology . . . 129--168
Stephen Alstrup and
Mikkel Thorup Optimal Pointer Algorithms for Finding
Nearest Common Ancestors in Dynamic
Trees . . . . . . . . . . . . . . . . . 169--188
Mikkel Thorup Floats, Integers, and Single Source
Shortest Paths . . . . . . . . . . . . . 189--201
Tsan-sheng Hsu On Four-Connecting a Triconnected Graph 202--234
Zhivko P. Nedev and
Peter T. Wood A Polynomial-Time Algorithm for Finding
Regular Simple Paths in Outerplanar
Graphs . . . . . . . . . . . . . . . . . 235--259
Anonymous Papers to Appear in Forthcoming Issues 260--260
Anonymous Author Index For Volume 35 . . . . . . . 261--261
Randeep Bhatia and
Samir Khuller and
Joseph (Seffi) Naor The Loading Time Scheduling Problem . . 1--33
Amihood Amir and
Gruia Calinescu Alphabet-Independent and Scaled
Dictionary Matching . . . . . . . . . . 34--62
Rolf Niedermeier and
Peter Rossmanith New Upper Bounds for Maximum
Satisfiability . . . . . . . . . . . . . 63--88
Hans Jürgen Prömel and
Angelika Steger A New Approximation Algorithm for the
Steiner Tree Problem with Performance
Ratio $5/3$ . . . . . . . . . . . . . . 89--101
Cyril Allauzen and
Mathieu Raffinot Simple Optimal String Matching Algorithm 102--116
Anonymous Papers to Appear in Forthcoming Issues 117--117
Jeannette Janssen and
Danny Krizanc and
Lata Narayanan and
Sunil Shende Distributed Online Frequency Assignment
in Cellular Networks . . . . . . . . . . 119--151
Rakesh Barve and
Mahesh Kallahalla and
Peter J. Varman and
Jeffrey Scott Vitter Competitive Parallel Disk Prefetching
and Buffer Management . . . . . . . . . 152--181
Bang Ye Wu and
Kun-Mao Chao and
Chuan Yi Tang A Polynomial Time Approximation Scheme
for Optimal Product-Requirement
Communication Spanning Trees . . . . . . 182--204
Elias Dahlhaus Parallel Algorithms for Hierarchical
Clustering and Applications to Split
Decomposition and Parity Graph
Recognition . . . . . . . . . . . . . . 205--240
Igor E. Shparlinski Computing Jacobi Symbols modulo Sparse
Integers and Polynomials and Some
Applications . . . . . . . . . . . . . . 241--252
Frédéric Havet Finding an Oriented Hamiltonian Path in
a Tournament . . . . . . . . . . . . . . 253--275
Anonymous Papers to Appear in Forthcoming Issues 276--276
Anonymous Author Index For Volume 36 . . . . . . . 277--277
Howard Karloff Foreword . . . . . . . . . . . . . . . . 1--1
András A. Benczúr and
David R. Karger Augmenting Undirected Edge Connectivity
in $\tilde{O}(n^2)$ Time . . . . . . . . 2--36
Martin Farach-Colton and
Vincenzo Liberatore On Local Register Allocation . . . . . . 37--65
Naveen Garg and
Goran Konjevod and
R. Ravi A Polylogarithmic Approximation
Algorithm for the Group Steiner Tree
Problem . . . . . . . . . . . . . . . . 66--84
David A. Grable and
Alessandro Panconesi Fast Distributed Algorithms for
Brooks--Vizing Colorings . . . . . . . . 85--120
Ming-Deh Huang and
Yiu-Chung Wong Extended Hilbert Irreducibility and Its
Applications . . . . . . . . . . . . . . 121--145
Madhukar R. Korupolu and
C. Greg Plaxton and
Rajmohan Rajaraman Analysis of a Local Search Heuristic for
Facility Location Problems . . . . . . . 146--188
Raimund Seidel and
Udo Adamy On the Exact Worst Case Query Complexity
of Planar Point Location . . . . . . . . 189--217
Neal E. Young On-Line Paging Against Adversarially
Biased Random Inputs . . . . . . . . . . 218--235
Anonymous Papers to Appear in Forthcoming Issues 236--236
Kaihong Xu The Asymptotic Worst-Case Behavior of
the FFD Heuristic for Small Items . . . 237--246
Amihood Amir and
Yonatan Aumann and
Gad M. Landau and
Moshe Lewenstein and
Noa Lewenstein Pattern Matching with Swaps . . . . . . 247--266
Kevin Cattell and
Frank Ruskey and
Joe Sawada and
Micaela Serra and
C. Robert Miers Fast Algorithms to Generate Necklaces,
Unlabeled Necklaces, and Irreducible
Polynomials over ${\rm GF}(2)$ . . . . . 267--282
Y. Boutalis and
C. Papaodysseus and
E. Koukoutsis A New Multichannel Recursive Least
Squares Algorithm for Very Robust and
Efficient Adaptive Filtering . . . . . . 283--308
Amihood Amir and
Dmitry Keselman and
Gad M. Landau and
Moshe Lewenstein and
Noa Lewenstein and
Michael Rodeh Text Indexing and Dictionary Matching
with One Error . . . . . . . . . . . . . 309--325
Jòrgen Bang-Jensen and
Tibor Jordán Splitting Off Edges within a Specified
Subset Preserving the Edge-Connectivity
of the Graph . . . . . . . . . . . . . . 326--343
Sorana Froda On Assessing the Performance of
Randomized Algorithms . . . . . . . . . 344--362
Md. Saidur Rahman and
Shin-ichi Nakano and
Takao Nishizeki Box-Rectangular Drawings of Plane Graphs 363--398
Michael T. Goodrich and
Christopher G. Wagner A Framework for Drawing Planar Graphs
with Curves and Polylines . . . . . . . 399--421
Amotz Bar-Noy and
Magnús M. Halldórsson and
Guy Kortsarz and
Ravit Salman and
Hadas Shachnai Sum Multicoloring of Graphs . . . . . . 422--450
Adam Smith and
Subhash Suri Rectangular Tiling in Multidimensional
Arrays . . . . . . . . . . . . . . . . . 451--467
Shay Kutten and
Rafail Ostrovsky and
Boaz Patt-Shamir The Las-Vegas Processor Identity Problem
(How and When to Be Unique) . . . . . . 468--494
David P. Jacobs and
Robert E. Jamison Complexity of Recognizing Equal Unions
in Families of Sets . . . . . . . . . . 495--504
Celina M. H. de Figueiredo and
Sulamita Klein and
Yoshiharu Kohayakawa and
Bruce A. Reed Finding Skew Partitions Efficiently . . 505--521
Sebastian Böcker and
David Bryant and
Andreas W. M. Dress and
Mike A. Steel Algorithmic Aspects of Tree Amalgamation 522--537
Subhas C. Nandy and
Bhargab B. Bhattacharya and
Antonio Hernández-Barrera Safety Zone Problem . . . . . . . . . . 538--569
David Eppstein Incremental and Decremental Maintenance
of Planar Width . . . . . . . . . . . . 570--577
Anonymous Papers to Appear in Forthcoming Issues 578--578
Anonymous Author Index For Volume 37 . . . . . . . 579--580
Bernard M. E. Moret Foreword . . . . . . . . . . . . . . . . 1--1
Bala Kalyanasundaram and
Kirk R. Pruhs Eliminating Migration in Multi-processor
Scheduling . . . . . . . . . . . . . . . 2--24
Jon Kleinberg and
Amit Kumar Wavelength Conversion in Optical
Networks . . . . . . . . . . . . . . . . 25--50
Andrew V. Goldberg and
Kostas Tsioutsiouliklis Cut Tree Algorithms: an Experimental
Study . . . . . . . . . . . . . . . . . 51--83
Piotr Indyk A Small Approximately Min-Wise
Independent Family of Hash Functions . . 84--90
Gill Barequet and
Sariel Har-Peled Efficiently Approximating the
Minimum-Volume Bounding Box of a Point
Set in Three Dimensions . . . . . . . . 91--109
Therese C. Biedl and
Prosenjit Bose and
Erik D. Demaine and
Anna Lubiw Efficient Algorithms for Petersen's
Matching Theorem . . . . . . . . . . . . 110--134
Jeffrey D. Oldham Combinatorial Approximation Algorithms
for Generalized Flow Problems . . . . . 135--169
Lenore J. Cowen Compact Routing with Minimum Stretch . . 170--183
Alan Siegel Median Bounds and Their Application . . 184--236
David Bryant and
Mike Steel Constructing Optimal Trees from Quartets 237--259
Madhukar R. Korupolu and
C. Greg Plaxton and
Rajmohan Rajaraman Placement Algorithms for Hierarchical
Cooperative Caching . . . . . . . . . . 260--302
Christian A. Duncan and
Michael T. Goodrich and
Stephen Kobourov Balanced Aspect Ratio Trees: Combining
the Advantages of $k$-d Trees and
Octrees . . . . . . . . . . . . . . . . 303--333
Anonymous Papers to Appear in Forthcoming Issues 334--334
Edith Cohen and
Uri Zwick All-Pairs Small-Stretch Paths . . . . . 335--353
Hiroshi Nagamochi and
Toru Hasunuma An Efficient $NC$ Algorithm for a Sparse
$k$-Edge-Connectivity Certificate . . . 354--373
Henning Fernau and
Rolf Niedermeier An Efficient Exact Algorithm for
Constraint Bipartite Vertex Cover . . . 374--410
Kazuhisa Makino and
Yushi Uno and
Toshihide Ibaraki On Minimum Edge Ranking Spanning Trees 411--437
Barun Chandra and
Magnús M. Halldórsson Approximation Algorithms for Dispersion
Problems . . . . . . . . . . . . . . . . 438--465
Anonymous Papers to Appear in Forthcoming Issues 466--466
Anonymous Author Index for Volume 38 . . . . . . . 467--467
Shay Halperin and
Uri Zwick Optimal Randomized EREW PRAM Algorithms
for Finding Spanning Forests . . . . . . 1--46
Evangelos Kranakis and
Danny Krizanc and
Andrzej Pelc Fault-Tolerant Broadcasting in Radio
Networks . . . . . . . . . . . . . . . . 47--67
Wei-Chang Yeh A Simple Algorithm for the Planar
Multiway Cut Problem . . . . . . . . . . 68--77
Josep Díaz and
Mathew D. Penrose and
Jordi Petit and
María Serna Approximating Layout Problems on Random
Geometric Graphs . . . . . . . . . . . . 78--116
Colin Cooper and
Martin Dyer and
Alan Frieze On Markov Chains for Randomly
${H}$-Coloring a Graph . . . . . . . . . 117--134
Anonymous Papers to Appear in Forthcoming Issues 135--135
Reuven Bar-Yehuda Using Homogeneous Weights for
Approximating the Partial Cover Problem 137--144
Kazuo Iwama and
Eiji Miyano A Lower Bound for Elementary Oblivious
Routing on Three-Dimensional Meshes . . 145--161
Gunnar Andersson and
Lars Engebretsen and
Johan Håstad A New Way of Using Semidefinite
Programming with Applications to Linear
Equations mod $p$ . . . . . . . . . . . 162--204
J. Ian Munro and
Venkatesh Raman and
S. Srinivasa Rao Space Efficient Suffix Trees . . . . . . 205--222
Barun Chandra and
Magnús M. Halldórsson Greedy Local Improvement and Weighted
Set Packing Approximation . . . . . . . 223--240
Anonymous Papers to Appear in Forthcoming Issues 241--241
Anonymous Author Index for Volume 39 . . . . . . . 242--242
Salvador Roura Digital Access to Comparison-Based Tree
Data Structures and Algorithms . . . . . 1--23
Anupam Gupta Improved Bandwidth Approximation for
Trees and Chordal Graphs . . . . . . . . 24--36
P. Flajolet and
X. Gourdon and
D. Panario The Complete Analysis of a Polynomial
Factorization Algorithm over Finite
Fields . . . . . . . . . . . . . . . . . 37--81
Xin He A Simple Linear Time Algorithm for
Proper Box Rectangular Drawings of Plane
Graphs . . . . . . . . . . . . . . . . . 82--101
Avner Dor and
Eitan Greenshtein An Almost-Greedy Search on Random Binary
Vectors and Random Graphs . . . . . . . 102--133
Anonymous Papers to Appear in Forthcoming Issues 134--134
Weimin Chen New Algorithm for Ordered Tree-to-Tree
Correction Problem . . . . . . . . . . . 135--158
Harold N. Gabow and
Haim Kaplan and
Robert E. Tarjan Unique Maximum Matching Algorithms . . . 159--183
Eran Halperin and
Uri Zwick Approximation Algorithms for MAX $4$-SAT
and Rounding Procedures for Semidefinite
Programs . . . . . . . . . . . . . . . . 184--211
Ming-Yang Kao and
Tak-Wah Lam and
Wing-Kin Sung and
Hing-Fung Ting An Even Faster and More Unifying
Algorithm for Comparing Trees via
Unbalanced Bipartite Matchings . . . . . 212--233
Anonymous Papers to Appear in Forthcoming Issues 234--234
Anonymous Author Index For Volume 40 . . . . . . . 235--235
Jòrgen Bang-Jensen and
Anders Yeo The Minimum Spanning Strong Subdigraph
Problem for Extended Semicomplete
Digraphs and Semicomplete Bipartite
Digraphs . . . . . . . . . . . . . . . . 1--19
Zhi-Zhong Chen Approximation Algorithms for Independent
Sets in Map Graphs . . . . . . . . . . . 20--40
Andrzej Lingas and
Hans Olsson and
Anna Östlin Efficient Merging and Construction of
Evolutionary Trees . . . . . . . . . . . 41--51
Gabriela Jeronimo and
Susana Puddu and
Juan Sabia Computing Chow Forms and Some
Applications . . . . . . . . . . . . . . 52--68
Torben Hagerup and
Peter Bro Miltersen and
Rasmus Pagh Deterministic Dictionaries . . . . . . . 69--85
Peter Sanders and
Roberto Solis-Oba How Helpers Hasten $h$-Relations . . . . 86--98
Michael Krivelevich and
Ram Nathaniel and
Benny Sudakov Approximating Coloring and Maximum
Independent Sets in 3-Uniform
Hypergraphs . . . . . . . . . . . . . . 99--113
Anonymous Papers to Appear in Forthcoming Issues 114--114
Houman Alborzi and
Eric Torng and
Patchrawat Uthaisombut and
Stephen Wagner The $k$-Client Problem . . . . . . . . . 115--173
Uriel Feige and
Michael Langberg Approximation Algorithms for
Maximization Problems Arising in Graph
Partitioning . . . . . . . . . . . . . . 174--211
Chandra Chekuri and
Michael Bender An Efficient Approximation Algorithm for
Minimizing Makespan on Uniformly Related
Machines . . . . . . . . . . . . . . . . 212--224
Leslie Ann Goldberg and
Paul W. Goldberg and
Mike Paterson and
Pavel Pevzner and
Süleyman Cenk Sahinalp and
Elizabeth Sweedyk The Complexity of Gene Placement . . . . 225--243
Peter Winkler Optimality and Greed in Dynamic
Allocation . . . . . . . . . . . . . . . 244--261
Kazuo Iwama and
Eiji Miyano An $O(N)$ Oblivious Routing Algorithm
for Two-Dimensional Meshes of Constant
Queue-Size . . . . . . . . . . . . . . . 262--279
Jianer Chen and
Iyad A. Kanj and
Weijia Jia Vertex Cover: Further Observations and
Further Improvements . . . . . . . . . . 280--301
Codrin Nichitiu and
Jacques Mazoyer and
Eric Rémila Algorithms for Leader Election by
Cellular Automata . . . . . . . . . . . 302--329
Timothy M. Chan and
Alon Efrat Fly Cheaply: On the Minimum Fuel
Consumption Problem . . . . . . . . . . 330--337
Gad M. Landau and
Michal Ziv-Ukelson On the Common Substring Alignment
Problem . . . . . . . . . . . . . . . . 338--359
Elias Dahlhaus and
Jens Gustedt and
Ross M. McConnell Efficient and Practical Algorithms for
Sequential Modular Decomposition . . . . 360--387
Milind Dawande and
Pinar Keskinocak and
Jayashankar M. Swaminathan and
Sridhar Tayur On Bipartite and Multipartite Clique
Problems . . . . . . . . . . . . . . . . 388--403
Amitabh Chaudhary and
Sundar Vishwanathan Approximation Algorithms for the
Achromatic Number . . . . . . . . . . . 404--416
Matthew Cary Toward Optimal $\epsilon$-Approximate
Nearest Neighbor Algorithms . . . . . . 417--428
Refael Hassin and
Samir Khuller $z$-Approximations . . . . . . . . . . . 429--442
Piotr Berman and
Bhaskar DasGupta and
S. Muthukrishnan and
Suneeta Ramaswami Efficient Approximation Algorithms for
Tiling and Packing Problems with
Rectangles . . . . . . . . . . . . . . . 443--470
Anonymous Papers to Appear in Forthcoming Issues 471--471
Anonymous Author Index For Volume 41 . . . . . . . 472--473
Ulrich Meyer and
Jop F. Sibeyn Oblivious Gossiping on Tori . . . . . . 1--19
Reuven Bar-Yehuda and
Dror Rawitz Approximating Element-Weighted Vertex
Deletion Problems for the Complete
$k$-Partite Property . . . . . . . . . . 20--40
Matti Nykänen and
Esko Ukkonen The Exact Path Length Problem . . . . . 41--53
Kouji Arata and
Satoru Iwata and
Kazuhisa Makino and
Satoru Fujishige Locating Sources to Meet Flow Demands in
Undirected Networks . . . . . . . . . . 54--68
Naomi Nishimura and
Prabhakar Ragde and
Dimitrios M. Thilikos On Graph Powers for Leaf-Labeled Trees 69--108
Dan Halperin and
Micha Sharir and
Ken Goldberg The 2-Center Problem with Obstacles . . 109--134
Pangfeng Liu Broadcast Scheduling Optimization for
Heterogeneous Cluster Systems . . . . . 135--152
C. R. Subramanian and
C. E. Veni Madhavan General Partitioning on Random Graphs 153--172
Takao Asano and
David P. Williamson Improved Approximation Algorithms for
MAX SAT . . . . . . . . . . . . . . . . 173--202
Anonymous Papers to Appear in Forthcoming Issues 203--203
Mikkel Thorup Randomized Sorting in $O(n \log \log n)$
Time and Linear Space Using Addition,
Shift, and Bit-wise Boolean Operations 205--230
Brenda S. Baker and
Raffaele Giancarlo Sparse Dynamic Programming for Longest
Common Subsequence from Fragments . . . 231--254
Mirela Damian-Iordache and
Sriram V. Pemmaraju A $(2 + \epsilon)$-Approximation Scheme
for Minimum Domination on Circle Graphs 255--276
Phil Bradford and
Mordecai J. Golin and
Lawrence L. Larmore and
Wojciech Rytter Optimal Prefix-Free Codes for Unequal
Letter Costs: Dynamic Programming with
the Monge Property . . . . . . . . . . . 277--303
Hatem M. Bahig and
Ken Nakamula Some Properties of Nonstar Steps in
Addition Chains and New Cases Where the
Scholz Conjecture Is True . . . . . . . 304--316
Nicholas Pippenger Analysis of Carry Propagation in
Addition: an Elementary Approach . . . . 317--333
Magnús M. Halldórsson and
Guy Kortsarz Tools for Multicoloring with
Applications to Planar Graphs and
Partial $k$-Trees . . . . . . . . . . . 334--366
Anonymous Papers to Appear in Forthcoming Issues 367--367
Anonymous Author Index For Volume 42 . . . . . . . 368--368
Wen-Lian Hsu A Simple Test for the Consecutive Ones
Property . . . . . . . . . . . . . . . . 1--16
Volker Heun and
Ernst W. Mayr Embedding Graphs with Bounded Treewidth
into Their Optimal Hypercubes . . . . . 17--50
Volker Heun and
Ernst W. Mayr Efficient Dynamic Embeddings of Binary
Trees into Hypercubes . . . . . . . . . 51--84
Robert W. Irving and
David F. Manlove The Stable Roommates Problem with Ties 85--105
Hans L. Bodlaender and
Dieter Kratsch Kayles and Nimbers . . . . . . . . . . . 106--119
E. G. Coffman, Jr. and
Predrag Jelenkovi\'c and
Petar Momcilovi\'c The Dyadic Stream Merging Algorithm . . 120--137
Daya Ram Gaur and
Toshihide Ibaraki and
Ramesh Krishnamurti Constant Ratio Approximation Algorithms
for the Rectangle Stabbing Problem and
the Rectilinear Partitioning Problem . . 138--152
Anonymous Erratum: Volume 41, Number 2 (2001), in
the article ``Approximation Algorithms
for the Achromatic Number,'' by Amitabh
Chaudhary and Sundar Vishwanathan, pages
404--416 . . . . . . . . . . . . . . . . 153--153
Anonymous Papers to Appear in Forthcoming Issues 154--154
Kazuhisa Makino A linear time algorithm for recognizing
regular Boolean functions . . . . . . . 155--176
Marek Chrobak and
Leszek G\kasieniec and
Wojciech Rytter Fast broadcasting and gossiping in radio
networks . . . . . . . . . . . . . . . . 177--189
Hans L. Bodlaender and
Fedor V. Fomin Approximation of pathwidth of
outerplanar graphs . . . . . . . . . . . 190--200
Uriel Feige and
Marek Karpinski and
Michael Langberg Improved approximation of Max-Cut on
graphs of bounded degree . . . . . . . . 201--219
Richard E. Stearns and
Harry B. Hunt III Exploiting structure in quantified
formulas . . . . . . . . . . . . . . . . 220--263
David Liben-Nowell Gossip is synteny: Incomplete gossip and
the syntenic distance between genomes 264--283
Anonymous Papers to appear in forthcoming issues 284--284
Anonymous Author Index for Volume 43 . . . . . . . 285--285
Helmut Prodinger and
Brigitte Vallée Preface . . . . . . . . . . . . . . . . 1--3
James Allen Fill and
Svante Janson Quicksort asymptotics . . . . . . . . . 4--28
Philippe Chassaing and
Guy Louchard Reflected Brownian Bridge area
conditioned on its local time at the
origin . . . . . . . . . . . . . . . . . 29--51
Ralph Neininger and
Ludger Rüschendorf Rates of convergence for Quicksort . . . 52--62
Charles Knessl and
Wojciech Szpankowski Limit laws for the height in PATRICIA
tries . . . . . . . . . . . . . . . . . 63--97
Theodoulos Garefalakis and
Daniel Panario Polynomials over finite fields free from
large and small degree irreducible
factors . . . . . . . . . . . . . . . . 98--120
Friedrich Hubalek and
Hsien-Kuei Hwang and
William Lew and
Hosam Mahmoud and
Helmut Prodinger A multivariate view of random bucket
digital search trees . . . . . . . . . . 121--158
Donatella Merlini and
Renzo Sprugnoli Fountains and histograms . . . . . . . . 159--176
Hua-Huai Chern and
Hsien-Kuei Hwang and
Tsung-Hsi Tsai An asymptotic theory for Cauchy--Euler
differential equations with applications
to the analysis of algorithms . . . . . 177--225
Amalia Duch and
Conrado Martínez On the average performance of orthogonal
range search in multidimensional data
structures . . . . . . . . . . . . . . . 226--245
Jérémie Bourdon and
Benoit Daireaux and
Brigitte Vallée Dynamical analysis of $\alpha$-Euclidean
algorithms . . . . . . . . . . . . . . . 246--285
Anonymous Papers to appear in forthcoming issues 286--286
Anonymous Editorial Board . . . . . . . . . . . . ??
Mauro Dell'Amico and
Lucian Finta A linear time algorithm for scheduling
outforests with communication delays on
three processors . . . . . . . . . . . . 287--307
János Csirik and
Gerhard J. Woeginger Resource augmentation for online bounded
space bin packing . . . . . . . . . . . 308--320
Vince Grolmusz Constructing set systems with prescribed
intersection sizes . . . . . . . . . . . 321--337
Richard Anderson and
Sampath Kannan and
Howard Karloff and
Richard E. Ladner Thresholds and optimal binary comparison
search trees . . . . . . . . . . . . . . 338--358
Bang Ye Wu A polynomial time approximation scheme
for the two-source minimum routing cost
spanning trees . . . . . . . . . . . . . 359--378
Anonymous Papers to appear in forthcoming issues 379--379
Anonymous Author index for volume 44 . . . . . . . 380--380
Anonymous Editorial Board . . . . . . . . . . . . ??
Kamal Jain and
Ion Mandoiu and
Vijay V. Vazirani and
David P. Williamson A primal-dual schema based approximation
algorithm for the element connectivity
problem . . . . . . . . . . . . . . . . 1--15
James Aspnes Fast deterministic consensus in a noisy
environment . . . . . . . . . . . . . . 16--39
Jan Kratochvíl and
Zsolt Tuza On the complexity of bicoloring clique
hypergraphs of graphs . . . . . . . . . 40--54
Tsan-sheng Hsu Simpler and faster biconnectivity
augmentation . . . . . . . . . . . . . . 55--71
Eran Halperin and
Ram Nathaniel and
Uri Zwick Coloring $k$-colorable graphs using
relatively small palettes . . . . . . . 72--90
Anonymous Papers to appear in forthcoming issues 91--91
Anonymous Editorial Board . . . . . . . . . . . . ??
Alberto Caprara and
Giuseppe F. Italiano and
G. Mohan and
Alessandro Panconesi and
Aravind Srinivasan Wavelength rerouting in optical
networks, or the Venetian Routing
Problem . . . . . . . . . . . . . . . . 93--125
Antonio Caruso and
Stefano Chessa and
Piero Maestrini and
Paolo Santi Diagnosability of regular systems . . . 126--143
David R. Wood Degree constrained book embeddings . . . 144--154
Gunnar Brinkmann and
Gilles Caporossi and
Pierre Hansen A constructive enumeration of fusenes
and benzenoids . . . . . . . . . . . . . 155--166
Klaus Jansen and
Lorant Porkolab Polynomial time approximation schemes
for general multiprocessor job shop
scheduling . . . . . . . . . . . . . . . 167--191
Tomás Feder and
Rajeev Motwani Worst-case time bounds for coloring and
satisfiability problems . . . . . . . . 192--201
Maurice Queyranne and
Maxim Sviridenko A $(2 + \epsilon)$-approximation
algorithm for the generalized preemptive
open shop problem with minsum objective 202--212
Anonymous Papers to Appear in Forthcoming Issues 213--213
Anonymous Author Index for Volume 45 . . . . . . . 214--214
Anonymous Editorial Board . . . . . . . . . . . . ??
Iris Gaber and
Yishay Mansour Centralized broadcast in multihop radio
networks . . . . . . . . . . . . . . . . 1--20
J. Sawada and
F. Ruskey Generating Lyndon brackets: an addendum
to: ``Fast algorithms to generate
necklaces, unlabeled necklaces and
irreducible polynomials over ${\rm
GF}(2)$ . . . . . . . . . . . . . . . . 21--26
Thomas Erlebach and
Frits C. R. Spieksma Interval selection: Applications,
algorithms, and lower bounds . . . . . . 27--53
Jeet Chaudhuri and
Subhas C. Nandy and
Sandip Das Largest empty rectangle among a point
set . . . . . . . . . . . . . . . . . . 54--78
Alexander Kesselman and
Yishay Mansour Loss-bounded analysis for differentiated
services . . . . . . . . . . . . . . . . 79--95
Anonymous Papers to appear in forthcoming issues 96--96
Anonymous Editorial Board . . . . . . . . . . . . ??
Anonymous Publisher's note . . . . . . . . . . . . iii--iv
Tamar Eilam and
Cyril Gavoille and
David Peleg Compact routing schemes with low stretch
factor . . . . . . . . . . . . . . . . . 97--114
Pankaj K. Agarwal and
Cecilia M. Procopiuc Approximation algorithms for projective
clustering . . . . . . . . . . . . . . . 115--139
Wei-Mei Chen and
Hsien-Kuei Hwang Analysis in distribution of two
randomized algorithms for finding the
maximum in a broadcast communication
model . . . . . . . . . . . . . . . . . 140--177
Timothy M. Chan Polynomial-time approximation schemes
for packing and piercing fat objects . . 178--189
Anonymous Papers to appear in forthcoming issues 190--190
Anonymous Author index for volume 46 . . . . . . . 191--191
Anonymous Editorial Board . . . . . . . . . . . . ??
Xiaotie Deng and
Guojun Li and
Wenan Zang and
Yi Zhou A 2-approximation algorithm for path
coloring on a restricted class of trees
of rings . . . . . . . . . . . . . . . . 1--13
Claudia Iturriaga and
Anna Lubiw Elastic labels around the perimeter of a
map . . . . . . . . . . . . . . . . . . 14--39
Konstantin Skodinis Construction of linear tree-layouts
which are optimal with respect to vertex
separation in linear time . . . . . . . 40--59
Hatem M. Bahig and
Ken Nakamula Erratum to ``Some properties of nonstar
steps in addition chains and new cases
where the Scholz conjecture is true'':
[J. Algorithms \bf 42 (2002) 304--316] 60--61
Anonymous Papers to appear in forthcoming issues 62--62
Anonymous Editorial Board . . . . . . . . . . . . ??
Rolf Niedermeier and
Peter Rossmanith On efficient fixed-parameter algorithms
for weighted vertex cover . . . . . . . 63--77
D. L. J. Alexander and
D. W. Bulger and
G. R. Wood Expected search duration for finite
backtracking adaptive search . . . . . . 78--86
Noga Alon and
Asaf Shapira Testing satisfiability . . . . . . . . . 87--103
Boaz Tsaban Permutation graphs, fast forward
permutations, and sampling the cycle
structure of a permutation . . . . . . . 104--121
Piotr Berman and
Bhaskar DasGupta and
S. Muthukrishnan Approximation algorithms for MAX-MIN
tiling . . . . . . . . . . . . . . . . . 122--134
Anonymous Papers to appear in forthcoming issues 135--135
Anonymous Author index for volume 47 . . . . . . . 136--136
Anonymous Editorial Board . . . . . . . . . . . . ??
Kirk Pruhs Foreword . . . . . . . . . . . . . . . . 1--1
Erik D. Demaine and
Alejandro López-Ortiz A linear lower bound on index size for
text retrieval . . . . . . . . . . . . . 2--15
Amos Fiat and
Haim Kaplan Making data structures confluently
persistent . . . . . . . . . . . . . . . 16--58
Amotz Bar-Noy and
Richard E. Ladner Competitive on-line stream merging
algorithms for media-on-demand . . . . . 59--90
Ulrich Meyer Average-case complexity of single-source
shortest-paths algorithms: lower and
upper bounds . . . . . . . . . . . . . . 91--134
Adrian Dumitrescu and
Joseph S. B. Mitchell Approximation algorithms for TSP with
neighborhoods in the plane . . . . . . . 135--159
Vijay Raghavan and
Jeremy Spinrad Robust algorithms for restricted domains 160--172
Katherine St. John and
Tandy Warnow and
Bernard M. E. Moret and
Lisa Vawter Performance study of phylogenetic
methods: (unweighted) quartet methods
and neighbor-joining . . . . . . . . . . 173--193
Ernst Althaus and
Denys Duchier and
Alexander Koller and
Kurt Mehlhorn and
Joachim Niehren and
Sven Thiel An efficient graph algorithm for
dominance constraints . . . . . . . . . 194--219
Refael Hassin and
Asaf Levin Minimum spanning tree with hop
restrictions . . . . . . . . . . . . . . 220--238
Alberto Caprara and
Alessandro Panconesi and
Romeo Rizzi Packing cycles in undirected graphs . . 239--256
Sudipto Guha and
Refael Hassin and
Samir Khuller and
Einat Or Capacitated vertex covering . . . . . . 257--270
Anonymous Papers to appear in forthcoming issues 271--271
Anonymous Editorial Board . . . . . . . . . . . . ??
Nodari Vakhania A better algorithm for sequencing with
release and delivery times on identical
machines . . . . . . . . . . . . . . . . 273--293
Kunihiko Sadakane New text indexing functionalities of the
compressed suffix arrays . . . . . . . . 294--313
Ashish Goel and
Monika R. Henzinger and
Serge Plotkin and
Eva Tardos Scheduling data transfers in a network
and the set scheduling problem . . . . . 314--332
Gruia Calinescu and
Cristina G. Fernandes and
Bruce Reed Multicuts in unweighted graphs and
digraphs with bounded degree and bounded
tree-width . . . . . . . . . . . . . . . 333--359
Leah Epstein and
Tamir Tassa Vector assignment problems: a general
framework . . . . . . . . . . . . . . . 360--384
Pascal Ferraro and
Christophe Godin Optimal mappings with minimum number of
connected components in tree-to-tree
comparison problems . . . . . . . . . . 385--406
Jens S. Frederiksen and
Kim S. Larsen and
John Noga and
Patchrawat Uthaisombut Dynamic TCP acknowledgment in the LogP
model . . . . . . . . . . . . . . . . . 407--428
Sudipto Guha and
Adam Meyerson and
Kamesh Munagala A constant factor approximation
algorithm for the fault-tolerant
facility location problem . . . . . . . 429--440
Chien-Chih Liao and
Hsueh-I Lu and
Hsu-Chun Yen Compact floor-planning via orderly
spanning trees . . . . . . . . . . . . . 441--451
Anonymous Papers to appear in forthcoming issues 452--452
Anonymous Author index for volume 48 . . . . . . . 453--453
Anonymous Editorial Board . . . . . . . . . . . . ??
Gianfranco Bilardi and
Giuseppe F. Italiano Preface . . . . . . . . . . . . . . . . 1--1
Michael Krivelevich and
Benny Sudakov Approximate coloring of uniform
hypergraphs . . . . . . . . . . . . . . 2--12
Danny Z. Chen and
Ovidiu Daescu and
Xiaobo (Sharon) Hu and
Jinhui Xu Finding an optimal path without growing
the tree . . . . . . . . . . . . . . . . 13--41
Johan Håstad and
Lars Ivansson and
Jens Lagergren Fitting points on the real line and its
application to RH mapping . . . . . . . 42--62
Bala Kalyanasundaram and
Kirk R. Pruhs Maximizing job completions online . . . 63--85
Daniele Frigioni and
Alberto Marchetti-Spaccamela and
Umberto Nanni Fully dynamic shortest paths in digraphs
with arbitrary arc weights . . . . . . . 86--113
U. Meyer and
P. Sanders $\Delta$-stepping: a parallelizable
shortest path algorithm . . . . . . . . 114--152
C. S. Helvig and
Gabriel Robins and
Alex Zelikovsky The moving-target traveling salesman
problem . . . . . . . . . . . . . . . . 153--174
Daniel W. Engels and
David R. Karger and
Stavros G. Kolliopoulos and
Sudipta Sengupta and
R. N. Uma and
Joel Wein Techniques for scheduling with rejection 175--191
Michael Fellows and
Michael Hallett and
Ulrike Stege Analogs & duals of the MAST problem for
sequences & trees . . . . . . . . . . . . 192--216
Anonymous Papers to appear in forthcoming issues 217--217
Anonymous Editorial Board . . . . . . . . . . . . ??
Zvika Brakerski and
Vladimir Dreizin and
Boaz Patt-Shamir Dispatching in perfectly-periodic
schedules . . . . . . . . . . . . . . . 219--239
Amihood Amir and
Gad M. Landau and
Dina Sokol Inplace $2$D matching in compressed
images . . . . . . . . . . . . . . . . . 240--261
Helmut Alt and
Alon Efrat and
Günter Rote and
Carola Wenk Matching planar maps . . . . . . . . . . 262--283
Sergei Bespamyatnikh Computing homotopic shortest paths in
the plane . . . . . . . . . . . . . . . 284--303
Anonymous Papers to appear in forthcoming issues 304--304
Anonymous Author index for volume 49 . . . . . . . 305--305
Anonymous Editorial Board . . . . . . . . . . . . ??
Sorina Dumitrescu and
Xiaolin Wu Algorithms for optimal multi-resolution
quantization . . . . . . . . . . . . . . 1--22
Markus Bläser An $8/13$-approximation algorithm for
the asymmetric maximum TSP . . . . . . . 23--48
Naveen Garg and
Vijay V. Vazirani and
Mihalis Yannakakis Multiway cuts in node weighted graphs 49--61
Md. Saidur Rahman and
Takao Nishizeki and
Shubhashis Ghosh Rectangular drawings of planar graphs 62--78
Lenore J. Cowen and
Christopher G. Wagner Compact roundtrip routing in directed
networks . . . . . . . . . . . . . . . . 79--95
Yijie Han Deterministic sorting in $O(n \log \log
n)$ time and linear space . . . . . . . 96--105
Weijia Jia and
Chuanlin Zhang and
Jianer Chen An efficient parameterized algorithm for
$m$-set packing . . . . . . . . . . . . 106--117
Noga Alon and
Gregory Gutin and
Michael Krivelevich Algorithms with large domination ratio 118--131
Anonymous Papers to appear in forthcoming issues 132--132
Anonymous Editorial Board . . . . . . . . . . . . ??
David Shmoys Foreword . . . . . . . . . . . . . . . . 133--133
Alexander Below and
Jesús A. De Loera and
Jürgen Richter-Gebert The complexity of finding small
triangulations of convex 3-polytopes . . 134--167
William Evans and
David Kirkpatrick Restructuring ordered binary trees . . . 168--193
Michel X. Goemans and
Martin Skutella Cooperative facility location games . . 194--214
László Babai and
Igor Pak Strong bias of group generators: an
obstacle to the ``product replacement
algorithm'' . . . . . . . . . . . . . . 215--231
Matthew Andrews Instability of FIFO in session-oriented
networks . . . . . . . . . . . . . . . . 232--245
Sundar Vishwanathan An approximation algorithm for finding
long paths in Hamiltonian graphs . . . . 246--256
Amihood Amir and
Moshe Lewenstein and
Ely Porat Faster algorithms for string matching
with $k$ mismatches . . . . . . . . . . 257--275
Anonymous Papers to appear in forthcoming issues 276--276
Anonymous Author index for volume 50 . . . . . . . 277--277
Anonymous Editorial Board . . . . . . . . . . . . ??
Jonathan Badger and
Paul Kearney and
Ming Li and
John Tsang and
Tao Jiang Selecting the branches for an
evolutionary tree.: a polynomial time
approximation scheme . . . . . . . . . . 1--14
Bernadette Charron-Bost and
André Schiper Uniform consensus is harder than
consensus . . . . . . . . . . . . . . . 15--37
Krzysztof Diks and
Pierre Fraigniaud and
Evangelos Kranakis and
Andrzej Pelc Tree exploration with little memory . . 38--63
George F. Georgakopoulos Splay trees: a reweighing lemma and a
proof of competitiveness vs. dynamic
balanced trees . . . . . . . . . . . . . 64--76
Stavros D. Nikolopoulos and
Leonidas Palios Parallel algorithms for ${P}$
$_4$-comparability graphs . . . . . . . 77--104
Anonymous Papers to appear in forthcoming issues 105--105
Anonymous Editorial Board . . . . . . . . . . . . ??
Magnus Wahlström Exact algorithms for finding minimum
transversals in rank-3 hypergraphs . . . 107--121
Rasmus Pagh and
Flemming Friche Rodler Cuckoo hashing . . . . . . . . . . . . . 122--144
Amotz Bar-Noy and
Grzegorz Malewicz Establishing wireless conference calls
under delay constraints . . . . . . . . 145--169
Alois Panholzer and
Helmut Prodinger and
Marko Riedel Permuting in place: analysis of two
stopping rules . . . . . . . . . . . . . 170--184
Vincenzo Liberatore Circular arrangements and cyclic
broadcast scheduling . . . . . . . . . . 185--215
Anonymous Papers to appear in forthcoming issues 216--216
Anonymous Author index for volume 51 . . . . . . . 217--217
Anonymous Editorial Board . . . . . . . . . . . . ??
Abraham Flaxman and
Alan Frieze and
Eli Upfal Efficient communication in an ad-hoc
network . . . . . . . . . . . . . . . . 1--7
Michael Elkin and
Guy Kortsarz Logarithmic inapproximability of the
radio broadcast problem . . . . . . . . 8--25
Jochen Alber and
Henning Fernau and
Rolf Niedermeier Parameterized complexity: exponential
speed-up for planar graph problems . . . 26--56
Matthew Andrews and
Lisa Zhang Minimizing end-to-end delay in
high-speed networks with a simple
coordinated schedule . . . . . . . . . . 57--81
Biing-Feng Wang and
Jyh-Jye Lin and
Shan-Chyun Ku Efficient algorithms for the scaled
indexing problem . . . . . . . . . . . . 82--100
Anonymous Papers to appear in forthcoming issues 101--101
Anonymous Editorial Board . . . . . . . . . . . . ??
Amr Elmasry Parameterized self-adjusting heaps . . . 103--119
Yossi Azar and
Leah Epstein and
Yossi Richter and
Gerhard J. Woeginger All-norm approximation algorithms . . . 120--133
Jochen Alber and
Jirí Fiala Geometric separation and exact solutions
for the parameterized independent set
problem on disk graphs . . . . . . . . . 134--151
J. Ellis and
H. Fan and
M. Fellows The dominating set problem is fixed
parameter tractable for graphs of
bounded genus . . . . . . . . . . . . . 152--168
Joan Boyar and
Susan Krarup and
Morten N. Nielsen Seat reservation allowing seat changes 169--192
Tak-Wah Lam and
Tsuen-Wan Johnny Ngan and
Kar-Keung To Performance guarantee for EDF under
overload . . . . . . . . . . . . . . . . 193--206
Anonymous Papers to appear in forthcoming issues 207--207
Anonymous Author index for volume 52 . . . . . . . 208--208
Anonymous Editorial Board . . . . . . . . . . . . ??
Boting Yang and
Cao An Wang Detecting tetrahedralizations of a set
of line segments . . . . . . . . . . . . 1--35
Fangting Sun and
David Fernández-Baca and
Wei Yu Inverse parametric sequence alignment 36--54
Rajiv Gandhi and
Samir Khuller and
Aravind Srinivasan Approximation algorithms for partial
covering problems . . . . . . . . . . . 55--84
Cyril Gavoille and
David Peleg and
Stéphane Pérennes and
Ran Raz Distance labeling in graphs . . . . . . 85--112
Anonymous Papers to appear in forthcoming issues 113--113
Anonymous Editorial Board . . . . . . . . . . . . ??
Michael A. Bender and
Ziyang Duan and
John Iacono and
Jing Wu A locality-preserving cache-oblivious
dynamic dictionary . . . . . . . . . . . 115--136
An Zhu Analysis of queueing policies in QoS
switches . . . . . . . . . . . . . . . . 137--168
Eran Halperin and
Dror Livnat and
Uri Zwick MAX CUT in cubic graphs . . . . . . . . 169--185
Lars Arge and
Gerth Stòlting Brodal and
Laura Toma On external-memory MST, SSSP and
multi-way planar graph separation . . . 186--206
Anonymous Papers to appear in forthcoming issues 207--207
Anonymous Author index for volume 53 . . . . . . . 208--208
Daniel J. Bernstein Factoring into coprimes in essentially
linear time . . . . . . . . . . . . . . 1--30
John M. Boyer Simple constant amortized time
generation of fixed length numeric
partitions . . . . . . . . . . . . . . . 31--39
Rainer Schuler An algorithm for the satisfiability
problem of formulas in conjunctive
normal form . . . . . . . . . . . . . . 40--44
Biing-Feng Wang Linear time algorithms for the ring
loading problem with demand splitting 45--57
Robin Pemantle A probabilistic model for the degree of
the cancellation polynomial in Gosper's
algorithm . . . . . . . . . . . . . . . 58--71
Robin Pemantle Cycles in random $k$-ary maps and the
poor performance of random number
generation . . . . . . . . . . . . . . . 72--84
S. Muthukrishnan and
Torsten Suel Approximation algorithms for array
partitioning problems . . . . . . . . . 85--104
Ben Gum and
Richard J. Lipton and
Andrea LaPaugh and
Faith Fich Estimating the maximum . . . . . . . . . 105--114
Dean Hoffman and
Peter Johnson and
Nadine Wilson Generating Huffman sequences . . . . . . 115--121
Martin Kochol 3-coloring and 3-clique-ordering of
locally connected graphs . . . . . . . . 122--125
Anonymous Papers to appear in forthcoming issues 126--126
Anonymous Editorial Board . . . . . . . . . . . . ??
James Aspnes and
Orli Waarts Compositional competitiveness for
distributed algorithms . . . . . . . . . 127--151
Kenneth Weber and
Vilmar Trevisan and
Luiz Felipe Martins A modular integer GCD algorithm . . . . 152--167
Richard Beigel and
David Eppstein $3$-coloring in time $O(n^{1.3289})$ . . 168--204
Mun-Kyu Lee and
Yoonjeong Kim and
Kunsoo Park and
Yookun Cho Efficient parallel exponentiation in
${\rm GF}(q n)$ using normal basis
representations . . . . . . . . . . . . 205--221
Anonymous Papers to appear in forthcoming issues 222--222
Anonymous Author index for volume 54 . . . . . . . 223--223
Anonymous Editorial Board . . . . . . . . . . . . ??
Ashish Goel and
Monika R. Henzinger and
Serge Plotkin An online throughput-competitive
algorithm for multicast routing and
admission control . . . . . . . . . . . 1--20
Michael Filaseta and
Douglas B. Meade Irreducibility testing of lacunary
0,1-polynomials . . . . . . . . . . . . 21--28
Petra \vSparl and
Janez \vZerovnik $2$-local $4/3$-competitive algorithm
for multicoloring hexagonal graphs . . . 29--41
Yoo-Ah Kim Data migration to minimize the total
completion time . . . . . . . . . . . . 42--57
Graham Cormode and
S. Muthukrishnan An improved data stream summary: the
count-min sketch and its applications 58--75
Reuven Bar-Yehuda and
Guy Even and
Shimon (Moni) Shahar On approximating a geometric
prize-collecting traveling salesman
problem with time windows . . . . . . . 76--92
Moni Naor On fairness in the carpool problem . . . 93--98
Anonymous Papers to appear in forthcoming issues 99--99
Anonymous Editorial Board . . . . . . . . . . . . ??
Micah Adler and
Adi Rosén Tight bounds for the performance of
Longest In System on DAGs . . . . . . . 101--112
William A. Aiello and
Yishay Mansour and
S. Rajagopolan and
Adi Rosén Competitive queue policies for
differentiated services . . . . . . . . 113--141
Alberto Del Lungo and
Guy Louchard and
Claudio Marini and
Franco Montagna The Guessing Secrets problem: a
probabilistic approach . . . . . . . . . 142--176
Benoit Larose and
Cynthia Loten and
László Zádori A polynomial-time algorithm for
near-unanimity graphs . . . . . . . . . 177--191
Yair Bartal and
Manor Mendel Randomized $k$-server algorithms for
growth-rate bounded graphs . . . . . . . 192--202
Anonymous Papers to appear in forthcoming issues 203--203
Anonymous Author index for volume 55 . . . . . . . 204--204
Anonymous Editorial Board . . . . . . . . . . . . ??
Dimitrios M. Thilikos and
Maria Serna and
Hans L. Bodlaender Cutwidth I: a linear time fixed
parameter algorithm . . . . . . . . . . 1--24
Dimitrios M. Thilikos and
Maria Serna and
Hans L. Bodlaender Cutwidth II: Algorithms for partial
$w$-trees of bounded degree . . . . . . 25--49
A. Tamir and
J. Puerto and
J. A. Mesa and
A. M. Rodríguez-Chía Conditional location of path and tree
shaped facilities on trees . . . . . . . 50--75
Anonymous Papers to appear in forthcoming issues 76--76
Anonymous Editorial Board . . . . . . . . . . . . ??
Hiroshi Nagamochi A $4/3$-approximation for the minimum
$2$-local-vertex-connectivity
augmentation in a connected graph . . . 77--95
Christine E. Heitsch Insufficiency of four known necessary
conditions on string unavoidability . . 96--123
Veli Mäkinen and
Gonzalo Navarro and
Esko Ukkonen Transposition invariant string matching 124--153
Anonymous Papers to appear in forthcoming issues 154--154
Anonymous Author index for volume 56 . . . . . . . 155--155
Anonymous Editorial Board . . . . . . . . . . . . ??
Feodor F. Dragan Estimating all pairs shortest paths in
restricted graph families: a unified
approach . . . . . . . . . . . . . . . . 1--21
Mark de Berg and
Joachim Gudmundsson and
Matthew J. Katz and
Christos Levcopoulos and
Mark H. Overmars and
A. Frank van der Stappen TSP with neighborhoods of varying size 22--36
René Sitters Complexity of preemptive minsum
scheduling on unrelated parallel
machines . . . . . . . . . . . . . . . . 37--48
Leah Epstein and
Lene M. Favrholdt Optimal non-preemptive semi-online
scheduling on two related machines . . . 49--73
Anonymous Papers to appear in forthcoming issues 74--74
Anonymous Editorial Board . . . . . . . . . . . . ??
Michael A. Bender and
Martín Farach-Colton and
Giridhar Pemmasani and
Steven Skiena and
Pavel Sumazin Lowest common ancestors in trees and
directed acyclic graphs . . . . . . . . 75--94
Rob van Stee and
Han La Poutré Minimizing the total completion time
on-line on a single machine, using
restarts . . . . . . . . . . . . . . . . 95--129
Tor Schoenmeyr and
David Yu Zhang FFT-based algorithms for the string
matching with mismatches problem . . . . 130--139
Oliver Schirokauer Virtual logarithms . . . . . . . . . . . 140--147
Anonymous Papers to appear in forthcoming issues 148--148
Anonymous Author index for volume 57 . . . . . . . 149--149
Anonymous Editorial Board . . . . . . . . . . . . ??
Zheng Sun and
John H. Reif On finding approximate optimal paths in
weighted regions . . . . . . . . . . . . 1--32
Anne Berry and
Jean-Paul Bordat and
Pinar Heggernes and
Genevi\`eve Simonet and
Yngve Villanger A wide-range algorithm for minimal
triangulation from an arbitrary ordering 33--66
Guillermo Durán and
Agustín Gravano and
Ross M. McConnell and
Jeremy Spinrad and
Alan Tucker Polynomial time recognition of unit
circular-arc graphs . . . . . . . . . . 67--78
Anonymous Papers to appear in forthcoming issues 79--79
Anonymous Editorial Board . . . . . . . . . . . . ??
Arye Barkan and
Haim Kaplan Partial alphabetic trees . . . . . . . . 81--103
Jop F. Sibeyn External selection . . . . . . . . . . . 104--117
Igor E. Zverovich A new kind of graph coloring . . . . . . 118--133
Ian F. Blake and
V. Kumar Murty and
Guangwu Xu Refinements of Miller's algorithm for
computing the Weil/Tate pairing . . . . 134--149
Aranyak Mehta and
Scott Shenker and
Vijay V. Vazirani Posted price profit maximization for
multicast by approximating fixed points 150--164
Anonymous Papers to appear in forthcoming issues 165--165
Anonymous Author index for volume 58 . . . . . . . 166--166
Anonymous Editorial Board . . . . . . . . . . . . ??
Esther M. Arkin and
Refael Hassin and
Asaf Levin Approximations for minimum and min-max
vehicle routing problems . . . . . . . . 1--18
Edith Cohen and
Martin J. Strauss Maintaining time-decaying stream
aggregates . . . . . . . . . . . . . . . 19--36
Monaldo Mastrolilli A linear time approximation scheme for
the single machine scheduling problem
with controllable processing times . . . 37--52
Nicholas J. A. Harvey and
Richard E. Ladner and
László Lovász and
Tami Tamir Semi-matchings for bipartite graphs and
load balancing . . . . . . . . . . . . . 53--78
Anonymous Papers to appear in forthcoming issues 79--79
Anonymous Editorial Board . . . . . . . . . . . . ??
Samir Khuller and
Yoo-Ah Kim and
Yung-Chun (Justin) Wan On generalized gossiping and
broadcasting . . . . . . . . . . . . . . 81--106
Biing-Feng Wang and
Shietung Peng and
Hong-Yi Yu and
Shan-Chyun Ku Efficient algorithms for a constrained
$k$-tree core problem in a tree network 107--124
Zhi-Zhong Chen and
Tatsuie Tsukiji Computing bounded-degree phylogenetic
roots of disconnected graphs . . . . . . 125--148
Bruce E. Sagan and
Jaejin Lee An algorithmic sign-reversing involution
for special rim-hook tableaux . . . . . 149--161
Anonymous Papers to appear in forthcoming issues 162--162
Anonymous Author index for volume 59 . . . . . . . 163--163
Anonymous Editorial Board . . . . . . . . . . . . ??
Uriel Feige and
Michael Langberg The RPR$^2$ rounding technique for
semidefinite programs . . . . . . . . . 1--23
Ilya Safro and
Dorit Ron and
Achi Brandt Graph minimum linear arrangement by
multilevel weighted edge contractions 24--41
Gagan Aggarwal and
Rajeev Motwani and
An Zhu The load rebalancing problem . . . . . . 42--59
Alex Kesselman and
Adi Rosén Scheduling policies for CIOQ switches 60--83
Anonymous Papers to appear in forthcoming issues 84--84
Anonymous Editorial Board . . . . . . . . . . . . ??
Andreas Jakoby and
Maciej Li\'skiewicz and
Rüdiger Reischuk Space efficient algorithms for directed
series-parallel graphs . . . . . . . . . 85--114
Artur Czumaj and
Wojciech Rytter Broadcasting algorithms in radio
networks with unknown topology . . . . . 115--143
Srinivas Kashyap and
Samir Khuller Algorithms for non-uniform size data
placement on parallel disks . . . . . . 144--167
Anonymous Papers to appear in forthcoming issues 168--168
Anonymous Author index for volume 60 . . . . . . . 169--169
Anonymous Editorial Board . . . . . . . . . . . . ??
Amin Coja-Oghlan and
Sven O. Krumke and
Till Nierhoff A heuristic for the Stacker Crane
Problem on trees which is almost surely
exact . . . . . . . . . . . . . . . . . 1--19
Petr Kolman and
Christian Scheideler Improved bounds for the unsplittable
flow problem . . . . . . . . . . . . . . 20--44
Anonymous Papers to appear in forthcoming issues 45--45
Anonymous Editorial Board . . . . . . . . . . . . ??
Simon R. Blackburn and
Domingo Gomez-Perez and
Jaime Gutierrez and
Igor E. Shparlinski Reconstructing noisy polynomial
evaluation in residue rings . . . . . . 47--59
Victor Chepoi and
Feodor F. Dragan and
Yann Vax\`es Distance and routing labeling schemes
for non-positively curved plane graphs 60--88
Anonymous Papers to appear in forthcoming issues 89--89
Anonymous Author index for volume 61 . . . . . . . 90--90
Anonymous Editorial Board . . . . . . . . . . . . ??
Tomás Feder and
Rajeev Motwani and
Liadan O'Callaghan and
Chris Olston and
Rina Panigrahy Computing shortest paths with
uncertainty . . . . . . . . . . . . . . 1--18
Amin Coja-Oghlan Solving NP-hard semirandom graph
problems in polynomial expected time . . 19--46
Anonymous Papers to appear in forthcoming issues 47--47
Anonymous Editorial Board . . . . . . . . . . . . ??
Sergio Cabello Approximation algorithms for spreading
points . . . . . . . . . . . . . . . . . 49--73
Surender Baswana and
Ramesh Hariharan and
Sandeep Sen Improved decremental algorithms for
maintaining transitive closure and
all-pairs shortest paths . . . . . . . . 74--92
Anonymous Editorial Board . . . . . . . . . . . . ??
Christiano Braga Special issue: LSFA'06 . . . . . . . . . 93--94
Narciso Martí-Oliet and
Miguel Palomino and
Alberto Verdejo Strategies and simulations in a semantic
framework . . . . . . . . . . . . . . . 95--116
Cláudia Nalon and
Clare Dixon Clausal resolution for normal modal
logics . . . . . . . . . . . . . . . . . 117--134
Benjamín Callejas Bedregal A normal form which preserves
tautologies and contradictions in a
class of fuzzy logics . . . . . . . . . 135--147
Robson da Luz and
Mírian Halfeld Ferrari and
Martin A. Musicante Regular expression transformations to
extend regular languages (with
application to a Datalog XML schema
validator) . . . . . . . . . . . . . . . 148--167
Anonymous Author index for volume 62 . . . . . . . 168--168
Anonymous Editorial Board . . . . . . . . . . . . ??
Marco Gavanelli and
Toni Mancini RCRA 2007: Experimental evaluation of
algorithms for solving problems with
combinatorial explosion . . . . . . . . 1--2
Joao Marques-Silva Model checking with Boolean
Satisfiability . . . . . . . . . . . . . 3--16
Gilles Audemard and
Said Jabbour and
Lakhdar Sais SAT graph-based representation: a new
perspective . . . . . . . . . . . . . . 17--33
F. Calimeri and
S. Perri and
F. Ricca Experimenting with parallelism for the
instantiation of ASP programs . . . . . 34--54
Luca Di Gaspero and
Andrea Roli Stochastic local search for large-scale
instances of the haplotype inference
problem by pure parsimony . . . . . . . 55--69
Marco Maratea and
Francesco Ricca and
Wolfgang Faber and
Nicola Leone Look-back techniques and heuristics in
DLV: Implementation, evaluation, and
comparison to QBF solvers . . . . . . . 70--89
Matti Järvisalo and
Ilkka Niemelä The effect of structural branching on
the efficiency of clause learning SAT
solving: an experimental study . . . . . 90--113
Richard J. Wallace and
Diarmuid Grimes Experimental studies of variable
selection strategies based on constraint
weights . . . . . . . . . . . . . . . . 114--129
Meritxell Vinyals and
Andrea Giovannucci and
Jesús Cerquides and
Pedro Meseguer and
Juan A. Rodriguez-Aguilar A test suite for the evaluation of mixed
multi-unit combinatorial auctions . . . 130--150
Anonymous Editorial Board . . . . . . . . . . . . ??
Yuriy Brun Solving satisfiability in the tile
assembly model with a constant-size
tileset . . . . . . . . . . . . . . . . 151--166
Jon Williamson Objective Bayesian probabilistic logic 167--183
Anonymous Editorial Board . . . . . . . . . . . . ??
Mauricio Osorio and
Ivan Olmos Preface . . . . . . . . . . . . . . . . 1--2
Stefania Costantini and
Andrea Formisano Modeling preferences and conditional
preferences on resource consumption and
production in ASP . . . . . . . . . . . 3--15
Roxana Danger and
Rafael Berlanga Generating complex ontology instances
from documents . . . . . . . . . . . . . 16--30
Alejandro Guerra-Hernández and
José Martín Castro-Manzano and
Amal El Fallah Seghrouchni CTL AgentSpeak(L): a specification
language for agent programs . . . . . . 31--40
Claudia Zepeda and
José Luis Carballido P-stable models of strong kernel
programs . . . . . . . . . . . . . . . . 41--50
David Pinto and
Jorge Civera and
Alberto Barrón-Cedeño and
Alfons Juan and
Paolo Rosso A statistical approach to crosslingual
natural language tasks . . . . . . . . . 51--60
Anonymous Editorial Board . . . . . . . . . . . . ??
Pierre Flener and
Justin Pearson Solving necklace constraint problems . . 61--73
Tongquan Zhang and
Weidong Li and
Jianping Li An improved approximation algorithm for
the ATSP with parameterized triangle
inequality . . . . . . . . . . . . . . . 74--78
C. Cortés and
J. M. Díaz-Báñez and
P. Pérez-Lantero and
C. Seara and
J. Urrutia and
I. Ventura Bichromatic separability with two boxes:
a general approach . . . . . . . . . . . 79--88
Hugo Jonker and
Sjouke Mauw and
Jun Pang A formal framework for quantifying
voter-controlled privacy . . . . . . . . 89--105
Jan Treur Past-future separation and normal forms
in temporal predicate logic
specifications . . . . . . . . . . . . . 106--124
Anonymous Editorial Board . . . . . . . . . . . . ??
Kostas Stathis and
Artur d'Avila Garcez and
Robert Givan Preface . . . . . . . . . . . . . . . . 125--126
Andriy Burkov and
Brahim Chaib-draa Effective learning in the presence of
adaptive counterparts . . . . . . . . . 127--138
Claudio A. Policastro and
Roseli A. F. Romero and
Giovana Zuliani and
Ednaldo Pizzolato Learning of shared attention in sociable
robotics . . . . . . . . . . . . . . . . 139--151
Verena Heidrich-Meisner and
Christian Igel Neuroevolution strategies for episodic
reinforcement learning . . . . . . . . . 152--168
Martijn van Otterlo Intensional dynamic programming. A
Rosetta stone for structured dynamic
programming . . . . . . . . . . . . . . 169--191
Anonymous Editorial Board . . . . . . . . . . . . ??
Michael T. Goodrich Randomized Shellsort: a Simple
Data-Oblivious Sorting Algorithm . . . . 27:1--27:??