Last update:
Wed Jul 9 22:45:55 MDT 2008
Don Coppersmith and
Andrew M. Odlyzko and
Richard Schroeppel Discrete logarithms in ${\rm GF}(p)$ . . 1--15
Christopher J. Van Wyk and
Jeffrey Scott Vitter The Complexity of Hashing with Lazy
Deletion . . . . . . . . . . . . . . . . 17--29
Robert Sedgewick and
Jeffrey Scott Vitter Shortest Paths in Euclidean Graphs . . . 31--48
Takao Asano and
Tetsuo Asano and
Leonidas J. Guibas and
John Hershberger and
Hiroshi Imai Visibility of Disjoint Polygons . . . . 49--63
Gianfranco Bilardi and
Franco P. Preparata Area-Time Lower-Bound Techniques with
Applications to Sorting . . . . . . . . 65--91
Herbert Edelsbrunner Edge-Skeletons in Arrangements with
Applications . . . . . . . . . . . . . . 93--109
Michael L. Fredman and
Robert Sedgewick and
Daniel Dominic Sleator and
Robert Endre Tarjan The Pairing Heap: A New Form of
Self-Adjusting Heap . . . . . . . . . . 111--129
Bernard Chazelle and
Leonidas J. Guibas Fractional Cascading: I. A Data
Structuring Technique . . . . . . . . . 133--162
Bernard Chazelle and
Leonidas J. Guibas Fractional cascading. II. Applications 163--191
D. T. Lee and
Y. F. Wu Geometric complexity of some location
problems . . . . . . . . . . . . . . . . 193--211
Kurt Mehlhorn and
Franco P. Preparata and
Majid Sarrafzadeh Channel Routing in Knock-Knee Mode:
Simplified Algorithms and Proofs . . . . 213--221
Shaodi Gao and
Susanne E. Hambrusch Two-Layer Channel Routing with Vertical
Uni-Length Overlap . . . . . . . . . . . 223--232
Richard A. Games Optimal Book Embeddings of the FFT,
Benes, and Barrel Shifter Networks . . . 233--250
Eugene W. Myers An $O(ND)$ Difference Algorithm and Its
Variations . . . . . . . . . . . . . . . 251--266
Calton Pu On-the-Fly, Incremental, Consistent
Reading of Entire Databases . . . . . . 271--287
Harry K. T. Wong and
Jianzhong Li and
Frank Olken and
Doron Rotem and
Linda Wong Bit Transposition for Very Large
Scientific and Statistical Databases . . 289--309
Hong-Tai Chou and
David J. DeWitt An Evaluation of Buffer Management
Strategies for Relational Database
Systems . . . . . . . . . . . . . . . . 311--336
Claudia Bauzer Medeiros and
Frank Wm. Tompa Understanding the Implications of View
Update Policies . . . . . . . . . . . . 337--360
Yannis E. Ioannidis A Time Bound on the Materialization of
Some Recursively Defined Views . . . . . 361--385
Nimrod Megiddo Introduction: New Approaches to Linear
Programming . . . . . . . . . . . . . . 387--394
Robert J. Vanderbei and
Marc S. Meketon and
Barry A. Freedman A Modification of Karmarkar's Linear
Programming Algorithm . . . . . . . . . 395--407
Michael J. Todd and
Bruce P. Burrell An Extension of Karmarkar's Algorithm
for Linear Programming Using Dual
Variables . . . . . . . . . . . . . . . 409--424
Guy de Ghellinck and
Jean-Philippe Vial A Polynomial Newton Method for Linear
Programming . . . . . . . . . . . . . . 425--453
Masao Iri and
Hiroshi Imai A Multiplicative Barrier Function Method
for Linear Programming . . . . . . . . . 455--482
Kurt M. Anstreicher A Monotonic Projective Algorithm for
Fractional Linear Programming . . . . . 483--498
Masakazu Kojima Determining Basic Variables of Optimal
Solutions in Karmarkar's New LP
Algorithm . . . . . . . . . . . . . . . 499--515
G. Rinaldi A Projective Method for Linear
Programming with Box-Type Constraints 517--527
J. L. Nazareth Homotopy Techniques in Linear
Programming . . . . . . . . . . . . . . 529--535
C. E. Blair The iterative step in the linear
programming algorithm of N. Karmarkar 537--539
Naoki Katoh and
Tiko Kameda and
Toshihide Ibaraki A Cautious Scheduler for Multistep
Transactions . . . . . . . . . . . . . . 1--26
Colm Ó'Dúnlaing and
Micha Sharir and
Chee K. Yap Generalized Vorono\uì diagrams for a
ladder. II. Efficient construction of
the diagram . . . . . . . . . . . . . . 27--59
Mark A. Shand Algorithms for Corner Stitched
Data-Structures . . . . . . . . . . . . 61--80
Eitan Zemel A Linear Time Randomizing Algorithm for
Searching Ranked Functions . . . . . . . 81--90
Daniel S. Hirschberg and
Lawrence L. Larmore The Set LCS Problem . . . . . . . . . . 91--95
Scot W. Hornick and
Majid Sarrafzadeh On Problem Transformability in VLSI . . 97--111
Richard M. Karp and
Frank Thomson Leighton and
Ronald L. Rivest and
Clark D. Thompson and
Umesh V. Vazirani and
Vijay V. Vazirani Global Wire Routing in Two-Dimensional
Arrays . . . . . . . . . . . . . . . . . 113--129
Claire Mathieu Some Problems in Computational Geometry 131--134
Bernard Chazelle Editor's Foreword . . . . . . . . . . . 135--136
Rex A. Dwyer A Faster Divide-and-Conquer Algorithm
for Constructing Delaunay Triangulations 137--151
Steven Fortune A Sweepline Algorithm for Vorono\uì
Diagrams . . . . . . . . . . . . . . . . 153--174
Christos Levcopoulos and
Andrzej Lingas On Approximation Behavior of the Greedy
Triangulation for Convex Polygons. . . . 175--193
Alok Aggarwal and
Maria M. Klawe and
Shlomo Moran and
Peter W. Shor and
Robert E. Wilber Geometric Applications of a
Matrix-Searching Algorithm . . . . . . . 195--208
Leonidas J. Guibas and
John Hershberger and
Daniel Leven and
Micha Sharir and
Robert Endre Tarjan Linear-Time Algorithms for Visibility
and Shortest Path Problems Inside
Triangulated Simple Polygons . . . . . . 209--233
Francis Y. Chin and
H. F. Ting An Improved Algorithm for Finding the
Median Distributively . . . . . . . . . 235--249
Pavol \vDuri\vs and
Ondrej Sýkora and
Clark D. Thompson and
Imrich V\vr\softto A minimum-area circuit for $l$-selection 251--265
Jean R. S. Blair and
Sanjiv Kapoor and
Errol L. Lloyd and
Kenneth J. Supowit Minimizing Channel Density in Standard
Cell Layout . . . . . . . . . . . . . . 267--282
Anna R. Karlin and
Howard W. Trickey and
Jeffrey D. Ullman Algorithms for the Compilation of
Regular Expressions into PLAs . . . . . 283--314
Alberto Apostolico and
C. Guerra The Longest Common Subsequence Problem
Revisited . . . . . . . . . . . . . . . 315--336
Bernard Chazelle Computing on a Free Tree via
Complexity-Preserving Mappings . . . . . 337--361
Chee-Keng Yap Preface Special Issue on Robotics . . . 363--365
Shmuel Sifrony and
Micha Sharir A New Efficient Motion-Planning
Algorithm for a Rod in Two-Dimensional
Polygonal Space . . . . . . . . . . . . 367--402
Vladimir J. Lumelsky and
Alexander A. Stepanov Path-Planning Strategies for a Point
Mobile Automaton Moving Amidst Unknown
Obstacles of Arbitrary Shape . . . . . . 403--430
Colm Ó'Dúnlaing Motion Planning with Inertial
Constraints . . . . . . . . . . . . . . 431--475
Michael Erdmann and
Tomás Lozano-Pérez On Multiple Moving Objects . . . . . . . 477--521
Christos H. Papadimitriou and
Ellen B. Silverberg Optimal Piecewise Linear Motion of an
Object Among Obstacles . . . . . . . . . 523--539
B. Mishra and
Jacob T. Schwartz and
Micha Sharir On the Existence and Synthesis of
Multifinger Positive Grips . . . . . . . 541--558
Jeffrey Scott Vitter Editor's Foreword: Special Issue on
Parallel and Distributed Computing, Part
I . . . . . . . . . . . . . . . . . . . 1--3
Jeffrey D. Ullman and
Allen Van Gelder Parallel Complexity of Logical Query
Programs . . . . . . . . . . . . . . . . 5--42
Faith E. Fich and
Prabhakar Ragde and
Avi Wigderson Simulations Among Concurrent-Write PRAMs 43--51
Charles E. Leiserson and
Bruce M. Maggs Communication-Efficient Parallel
Algorithms for Distributed Random-Access
Machines . . . . . . . . . . . . . . . . 53--77
Anna R. Karlin and
Mark S. Manasse and
Larry Rudolph and
Daniel Dominic Sleator Competitive Snoopy Caching . . . . . . . 79--119
Yoram Moses and
Mark R. Tuttle Programming Simultaneous Actions Using
Common Knowledge . . . . . . . . . . . . 121--169
Greg N. Frederickson and
Ravi Janardan Designing Networks with Compact Routing
Tables . . . . . . . . . . . . . . . . . 171--190
Marshall W. Bern Two Probabilistic Results on Rectilinear
Steiner Trees . . . . . . . . . . . . . 191--204
Bernard Chazelle An Algorithm for Segment-Dragging and
Its Implementation . . . . . . . . . . . 205--221
Hyeong-Ah Choi and
S. Louis Hakimi Data Transfers in Networks . . . . . . . 223--245
Jayaram Bhasker and
Sartaj Sahni A Linear Algorithm to Find a Rectangular
Dual of a Planar Triangulated Graph . . 247--278
Chee-Keng Yap Parallel Triangulation of a Polygon in
Two Calls to the Trapezoidal Map . . . . 279--288
Jeffrey Scott Vitter Editor's Foreword: Special Issue on
Parallel and Distributed Computing, Part
II . . . . . . . . . . . . . . . . . . . 289--291
Alok Aggarwal and
Bernard Chazelle and
Leonidas J. Guibas and
Colm Ó'Dúnlaing and
Chee K. Yap Parallel Computational Geometry . . . . 293--327
Richard Cole and
Uzi Vishkin The Accelerated Centroid Decomposition
Technique for Optimal Parallel Tree
Evaluation in Logarithmic Time . . . . . 329--346
Alberto Apostolico and
Costas S. Iliopoulos and
Gad M. Landau and
Baruch Schieber and
Uzi Vishkin Parallel Construction of a Suffix Tree
with Applications . . . . . . . . . . . 347--365
Sape J. Mullender and
Paul M. B. Vitányi Distributed Match-Making . . . . . . . . 367--391
Rivka Ladin and
Barbara Liskov and
Liuba Shrira A Technique for Constructing Highly
Available Services . . . . . . . . . . . 393--420
Paris C. Kanellakis and
Scott A. Smolka On the Analysis of Cooperation and
Antagonism in Networks of Communicating
Processes . . . . . . . . . . . . . . . 421--450
Foto N. Afrati and
Christos H. Papadimitriou and
George Papageorgiou The Synthesis of Communication Protocols 451--472
David P. Dobkin and
Diane L. Souvaine and
Christopher J. Van Wyk Decomposition and Intersection of Simple
Splinegons . . . . . . . . . . . . . . . 473--485
Paul Czerwinski and
Vijaya Ramachandran Optimal VLSI Graph Embeddings in
Variable Aspect Ratio Rectangles . . . . 487--510
Paul A. Peterson and
Michael C. Loui The general maximum matching algorithm
of Micali and Vazirani . . . . . . . . . 511--533
Mikhail J. Atallah and
Michael T. Goodrich Parallel Algorithms for Some Functions
of two Convex Polygons . . . . . . . . . 535--548
Michael R. Fellows and
Donald K. Friesen and
Michael A. Langston On Finding Optimal and Near-Optimal
Lineal Spanning Trees . . . . . . . . . 549--560
John M. Marberg and
Eli Gafni Sorting in Constant Number of Row and
Column Phases on a Mesh . . . . . . . . 561--572
Chee-Keng Yap Editor's Foreword: Special Issue on
Computational Geometry . . . . . . . . . 1--2
David P. Dobkin and
Michael J. Laszlo Primitives for the Manipulation of
Three-Dimensional Subdivisions . . . . . 3--32
Robert L. (Scot) Drysdale III and
Robert B. Jerard and
Barry Schaudt and
Ken Hauck Discrete Simulation of NC Machining . . 33--60
Masato Edahiro and
Katsuhiko Tanaka and
Takashi Hoshino and
Takao Asano A Bucketing Algorithm for the Orthogonal
Segment Intersection Search Problem and
Its Practical Efficiency . . . . . . . . 61--76
Hiroshi Imai and
Kenji Kato and
Peter Yamamoto A Linear-Time Algorithm for Linear $L_1$
Approximation of Points . . . . . . . . 77--96
L. Paul Chew Constrained Delaunay Triangulations . . 97--108
Boris Aronov On the Geodesic Vorono\uì Diagram of
Point Sites in a Simple Polygon . . . . 109--140
John Hershberger An Optimal Visibility Graph Algorithm
for Triangulated Simple Polygons . . . . 141--155
Chandrajit L. Bajaj and
Myung-Soo Kim Generation of Configuration Space
Obstacles: The Case of Moving Algebraic
Curves . . . . . . . . . . . . . . . . . 157--172
David Fernández-Baca and
Charles U. Martel On the Efficiency of Maximum-Flow
Algorithms on Networks with Small
Integer Capacities . . . . . . . . . . . 173--189
Dana S. Richards Fast Heuristic Algorithms for
Rectilinear Steiner Trees . . . . . . . 191--207
Joseph Y.-T. Leung A new algorithm for scheduling periodic,
real-time tasks . . . . . . . . . . . . 209--219
Mikhail J. Atallah and
S. Rao Kosaraju An Efficient Algorithm for Maxdominance,
with Applications . . . . . . . . . . . 221--236
Shang-Ching Chou and
Jin Gen Yang On the Algebraic Formulation of Certain
Geometry Statements and Mechanical
Geometry Theorem Proving . . . . . . . . 237--262
D. F. Wong and
C. L. Liu Floorplan Design of VLSI Circuits . . . 263--291
Andrew Chi-Chih Yao On selecting the $k$ largest with median
tests . . . . . . . . . . . . . . . . . 293--300
Israel Cidon and
Inder Gopal Editor's Foreword: Special Issue on
Algorithmic Aspects of Communications 301--302
Sergio Verdú Computational Complexity of Optimum
Multiuser Detection . . . . . . . . . . 303--312
Michael Paterakis and
L. Georgiadis and
P. Papantoni-Kazakos A Full Sensing Window Random-Access
Algorithm for Messages with Strict Delay
Constraints . . . . . . . . . . . . . . 313--328
Yaron I. Gold and
Shlomo Moran A Correction Algorithm for Token-Passing
Sequences in Mobile Communication
Networks . . . . . . . . . . . . . . . . 329--341
Jeffrey M. Jaffe and
Zvi Rosberg Maximal Selection in Tandem Networks
with Symmetric Hearing Range . . . . . . 343--364
M. J. Post and
A. S. Kershenbaum and
P. E. Sarachik Scheduling Multihop CDMA Networks in the
Presence of Secondary Conflicts . . . . 365--393
Jonathan L. Wang and
John A. Silvester Optimizing Responses to Broadcast
Messages in Radio Networks . . . . . . . 395--416
Jeffrey M. Jaffe and
Moshe Sidi Distributed Deadlock Resolution in
Store-and-Forward Networks . . . . . . . 417--436
Hagit Attiya and
Jan van Leeuwen and
Nicola Santoro and
Shmuel Zaks Efficient Elections in Chordal Ring
Networks . . . . . . . . . . . . . . . . 437--446
Sanjiv Kapoor and
Prakash V. Ramanan Lower Bounds for Maximal and Convex
Layers Problems . . . . . . . . . . . . 447--459
Kenneth L. Clarkson An Algorithm for Geometric Minimum
Spanning Trees Requiring Nearly Linear
Expected Time . . . . . . . . . . . . . 461--469
Hitoshi Suzuki and
Takao Nishizeki and
Nobuji Saito Algorithms for Multicommodity Flows in
Planar Graphs . . . . . . . . . . . . . 471--501
Daniel S. Hirschberg and
Lawrence L. Larmore The Set-Set LCS Problem . . . . . . . . 503--510
Nimrod Megiddo Extending NC and RNC Algorithms . . . . 511--517
Prakash V. Ramanan and
Kazuhiro Tsuga Average-Case Analysis of the Modified
Harmonic Algorithm . . . . . . . . . . . 519--533
Rolf Klein and
Otto Nurmi and
Thomas Ottmann and
Derick Wood A Dynamic Fixed Windowing Problem . . . 535--550
Michael Luby and
Prabhakar Ragde A Bidirectional Shortest-Path Algorithm
with Good Average-Case Behavior . . . . 551--567
Pravin M. Vaidya Approximate minimum weight matching on
points in $k$-dimensional space . . . . 569--583
Elena Lodi and
Fabrizio Luccio and
Linda Pagli A Preliminary Study of a Diagonal
Channel-Routing Model . . . . . . . . . 585--597
Steven S. Skiena Problems in Geometric Probing . . . . . 599--605
Benny Chor and
Oded Goldreich An Improved Parallel Algorithm for
Integer GCD . . . . . . . . . . . . . . 1--10
Teofilo F. Gonzalez and
Si-Qing Zheng Approximation Algorithms for
Partitioning a Rectangle with Interior
Points . . . . . . . . . . . . . . . . . 11--42
Clyde P. Kruskal and
Larry Rudolph and
Marc Snir Efficient Parallel Algorithms for Graph
Problems . . . . . . . . . . . . . . . . 43--64
M. Orlowski A New Algorithm for the Largest Empty
Rectangle Problem . . . . . . . . . . . 65--73
Michael S. Paterson Improved Sorting Networks with $O(\log
N)$ Depth . . . . . . . . . . . . . . . 75--92
Daniel Bienstock and
Clyde L. Monma On the Complexity of Embedding Planar
Graphs To Minimize Certain Distance
Measures . . . . . . . . . . . . . . . . 93--109
Ding Zhu Du and
Yanjun Zhang On Heuristics for Minimum Length
Rectilinear Partitions . . . . . . . . . 111--128
Xin He and
Yaacov Yesha Efficient parallel algorithms for
$r$-dominating set and $p$-center
problems on trees . . . . . . . . . . . 129--145
Shang-Ching Chou and
William F. Schelter and
Jin Gen Yang An Algorithm for Constructing Gröbner
Bases from Characteristic Sets and Its
Application to Geometry . . . . . . . . 147--154
C. S. Jeong and
D. T. Lee Parallel Geometric Algorithms on a
Mesh-Connected Computer . . . . . . . . 155--177
Carla D. Savage and
Matthias Stallmann and
Jo Ellen Perry Solving Some Combinatorial Problems on
Arrays with One-Way Dataflow . . . . . . 179--199
S. Sudarshan and
C. Pandu Rangan A Fast Algorithm for Computing Sparse
Visibility Graphs . . . . . . . . . . . 201--214
Kurt Mehlhorn and
Stefan Näher Dynamic Fractional Cascading . . . . . . 215--241
Ian Parberry An Optimal Time Bound for Oblivious
Routing . . . . . . . . . . . . . . . . 243--250
Gabriele Blankenagel and
Ralf Hartmut Güting Internal and external algorithms for the
points-in-regions problem---the INSIDE
join of geo-relational algebra . . . . . 251--276
Israel Cidon and
Inder S. Gopal Dynamic Detection of Subgraphs in
Computer Networks . . . . . . . . . . . 277--294
Joseph C. Culberson and
J. Ian Munro Analysis of the Standard Deletion
Algorithms in Exact Fit Domain Binary
Search Trees . . . . . . . . . . . . . . 295--311
Esko Ukkonen A Linear-Time Algorithm for Finding
Approximate Shortest Common Superstrings 313--323
Friedemann Mattern Asynchronous Distributed
Termination-Parallel and Symmetric
Solutions with Echo Algorithms . . . . . 325--340
M. T. Ko and
R. C. T. Lee and
J. S. Chang An optimal approximation algorithm for
the rectilinear $m$-center problem . . . 341--352
Bruce Randall Donald The Complexity of Planar Compliant
Motion Planning Under Uncertainty . . . 353--382
Michael M. Wu and
Michael C. Loui An Efficient Distributed Algorithm for
Maximum Matching in General Graphs . . . 383--406
Clyde L. Monma and
Michael S. Paterson and
Subhash Suri and
F. Frances Yao Computing Euclidean Maximum Spanning
Trees . . . . . . . . . . . . . . . . . 407--419
David P. Dobkin and
Diane L. Souvaine Computational Geometry in a Curved World 421--457
Bonnie Berger and
John Rompel A Better Performance Guarantee for
Approximate Graph Coloring . . . . . . . 459--466
Yen Tai Lai and
Sany M. Leinwand A Theory of Rectangular Dual Graphs . . 467--483
Sang Ho Lee and
Kyung-Yong Chwa Some Chain Visibility Problems in a
Simple Polygon . . . . . . . . . . . . . 485--507
Roberto Tamassia and
Franco P. Preparata Dynamic Maintenance of Planar Digraphs,
with Applications . . . . . . . . . . . 509--527
Fabrizio Luccio and
Andrea Pietracaprina and
Geppino Pucci A New Scheme for the Deterministic
Simulation of PRAMs in VLSI . . . . . . 529--544
Xin He Efficient parallel and sequential
algorithms for $4$-coloring perfect
planar graphs . . . . . . . . . . . . . 545--559
David P. Dobkin and
Herbert Edelsbrunner and
Mark H. Overmars Searching for Empty Convex Polygons . . 561--571
Panagiotis Alevizos and
Jean-Daniel Boissonnat and
Franco P. Preparata An Optimal Algorithm for the Boundary of
a Cell in a Union of Rays . . . . . . . 573--590
F. K. Hwang and
Y. C. Yao Comments on Bern's Probabilistic Results
on Rectilinear Steiner Trees . . . . . . 591--598
Andrea S. LaPaugh and
Frank Thomson Leighton Editors' Introduction . . . . . . . . . 1--3
Charles E. Leiserson and
James B. Saxe Retiming Synchronous Circuitry . . . . . 5--35
Sandeep N. Bhatt and
Fan R. K. Chung and
Arnold L. Rosenberg Partitioning Circuits for Improved
Testability . . . . . . . . . . . . . . 37--48
Alok Aggarwal and
J. Lawrence Carter and
S. Rao Kosaraju Optimal Tradeoffs for Addition on
Systolic Arrays . . . . . . . . . . . . 49--71
Prabhakar Raghavan and
Clark Thomborson Multiterminal Global Routing: A
Deterministic Approximation Scheme . . . 73--82
Martin L. Brady and
Donna J. Brown Optimal Multilayer Channel Routing with
Overlap . . . . . . . . . . . . . . . . 83--101
F. Miller Maley A Generic Algorithm for One-Dimensional
Homotopic Compaction . . . . . . . . . . 103--128
Alok Aggarwal and
Maria M. Klawe and
Peter W. Shor Multilayer Grid Embeddings for VLSI . . 129--151
Clovis C. Gonzaga Search Directions for Interior
Linear-Programming Methods . . . . . . . 153--181
Hans Rohnert Moving a Disc Between Polygons . . . . . 182--191
D. F. Wong and
Edward M. Reingold Probabilistic Analysis of a Grouping
Algorithm . . . . . . . . . . . . . . . 192--206
Gary M. Shute and
Linda L. Deneen and
Clark D. Thomborson An $O(n \log n)$ Plane-Sweep Algorithm
for $L_1$ and $L_\infty$ Delaunay
Triangulations . . . . . . . . . . . . . 207--221
Sally Floyd and
Richard M. Karp FFD Bin Packing for Item Sizes with
Uniform Distributions on $[0,\frac12]$ 222--240
Alok Aggarwal and
Maria M. Klawe and
David Lichtenstein and
Nathan Linial and
Avi Wigderson A Lower Bound on the Area of Permutation
Layouts . . . . . . . . . . . . . . . . 241--255
Wojciech Szpankowski On the Height of Digital Trees and
Related Problems . . . . . . . . . . . . 256--277
Sanjiv Kapoor and
Edward M. Reingold Stochastic Rearrangement Rules for
Self-Organizing Data Structures . . . . 278--291
Panagiotis Alevizos and
Jean-Daniel Boissonnat and
Franco P. Preparata Corrigendum: ``An optimal algorithm for
the boundary of a cell in a union of
rays'' [Algorithmica \bf 5 (1990), no.\
4, 573--590; MR1072808 (91g:68154)] . . 292--293
Alberto L. Sangiovanni-Vincentelli Editor's Foreword . . . . . . . . . . . 295--301
Fabio Romeo and
Alberto L. Sangiovanni-Vincentelli A Theoretical Framework for Simulated
Annealing . . . . . . . . . . . . . . . 302--345
Philip N. Strenski and
Scott Kirkpatrick Analysis of Finite Length Annealing
Schedules . . . . . . . . . . . . . . . 346--366
Gregory B. Sorkin Efficient Simulated Annealing on Fractal
Energy Landscapes . . . . . . . . . . . 367--418
Saul B. Gelfand and
Sanjoy K. Mitter Simulated Annealing Type Algorithms for
Multivariate Optimization . . . . . . . 419--436
Emile H. L. Aarts and
Jan H. M. Korst Boltzmann Machines as a Model for
Parallel Annealing . . . . . . . . . . . 437--465
Eugene Wong Stochastic Neural Networks . . . . . . . 466--478
Vince Grolmusz Large Parallel Machines Can Be Extremely
Slow for Small Problems . . . . . . . . 479--489
Harald Rosenberger Order-$k$ Vorono\uì diagrams of sites
with additive weights in the plane . . . 490--521
Leila De Floriani and
Bianca Falcidieno and
George Nagy and
Caterina Pienovi On Sorting Triangles in a Delaunay
Tessellation . . . . . . . . . . . . . . 522--532
Chandrajit L. Bajaj and
Myung-Soo Kim Convex Hulls of Objects Bounded by
Algebraic Curves . . . . . . . . . . . . 533--553
Daniel M. Gordon Parallel Sorting on Cayley Graphs . . . 554--564
S. Alice Wu and
Joseph JáJá Optimal Algorithms for Adjacent Side
Routing . . . . . . . . . . . . . . . . 565--578
Robert F. Sproull Refinements to nearest-neighbor
searching in $k$-dimensional trees . . . 579--589
J. B. Kruskal and
Albert G. Greenberg A Flexible Way of Counting Large Numbers
Approximately in Small Registers . . . . 590--596
Claire M. Kenyon and
Jeffrey Scott Vitter Maximum Queue Size and Hashing with Lazy
Deletion . . . . . . . . . . . . . . . . 597--619
Frank K. H. A. Dehne Editor's Foreword Special Issue on
Parallel Algorithms for Geometric
Problems on Digitized Pictures . . . . . 621--623
Dipen Moitra Finding a Minimal Cover for Binary
Images: An Optimal Parallel Algorithm 624--657
Russ Miller and
Quentin F. Stout Computing Convexity Properties of Images
on a Pyramid Computer . . . . . . . . . 658--684
Otfried Schwarzkopf Parallel Computation of Distance
Transforms . . . . . . . . . . . . . . . 685--697
Hussein M. Alnuweiri and
V. K. Prasanna Kumar Processor-Time Optimal Parallel
Algorithms for Digitized Images on
Mesh-Connected Processor Arrays . . . . 698--733
Frank K. H. A. Dehne and
A.-L. Hassenklover and
Jörg-Rüdiger Sack and
Nicola Santoro Computational Geometry Algorithms for
the Systolic Screen . . . . . . . . . . 734--761
Mikhail J. Atallah and
Susanne E. Hambrusch and
Lynn E. Te Winkel Topological Numbering of Features on a
Mesh . . . . . . . . . . . . . . . . . . 762--769
Robon Liu and
Simeon C. Ntafos On Partitioning Rectilinear Polygons
into Star-Shaped Polygons . . . . . . . 771--800
Marek Chrobak and
Joseph Naor An Efficient Parallel Algorithm for
Computing a Large Independent Set in a
Planar Graph . . . . . . . . . . . . . . 801--815
Lyle A. McGeoch and
Daniel Dominic Sleator A Strongly Competitive Randomized Paging
Algorithm . . . . . . . . . . . . . . . 816--825
Shigeru Masuyama and
Toshihide Ibaraki Chain Packing in Graphs . . . . . . . . 826--839
Marc J. van Kreveld and
Mark H. Overmars Divided $k$-$d$ trees . . . . . . . . . 840--858
Richard J. Anderson and
Gary L. Miller Deterministic Parallel List Ranking . . 859--868
Craig A. Morgenstern and
Henry D. Shapiro Heuristics for Rapidly Four-Coloring
Large Planar Graphs . . . . . . . . . . 869--891
Alok Aggarwal Editor's Foreword . . . . . . . . . . . 1--2
Richard Cole and
Michael T. Goodrich Optimal Parallel Algorithms for
Point-Set and Polygon Problems . . . . . 3--23
Sharat Chandran and
Sung Kwon Kim and
David M. Mount Parallel Computational Geometry of
Rectangles . . . . . . . . . . . . . . . 25--49
Ed Cohen and
Russ Miller and
Elias M. Sarraf and
Quentin F. Stout Efficient convexity and domination
algorithms for fine- and medium-grain
hypercube computers . . . . . . . . . . 51--75
Jorge L. C. Sanz and
Robert Cypher Data Reduction and Fast Routing: A
Strategy for Efficient Algorithms for
Message-Passing Parallel Computers . . . 77--89
John H. Reif and
Sandeep Sen Optimal Randomized Parallel Algorithms
for Computational Geometry . . . . . . . 91--117
F. K. Hwang Foreword . . . . . . . . . . . . . . . . 119--120
Ding-Zhu Du and
F. K. Hwang A proof of the Gilbert--Pollak
conjecture on the Steiner ratio . . . . 121--135
Warren D. Smith How to find Steiner minimal trees in
Euclidean $d$-space . . . . . . . . . . 137--177
Zi Cheng Liu and
Ding Zhu Du On Steiner Minimal Trees with $L_p$
Distance . . . . . . . . . . . . . . . . 179--191
J. H. Rubinstein and
D. A. Thomas Graham's Problem on Shortest Networks
for Points on a Circle . . . . . . . . . 193--218
E. J. Cockayne and
D. E. Hewgill Improved Computation of Plane Steiner
Minimal Trees . . . . . . . . . . . . . 219--229
R. S. Booth and
J. F. Weng Steiner Minimal Trees for a Class of
Zigzag Lines . . . . . . . . . . . . . . 231--246
Dana S. Richards and
Jeffrey S. Salowe A linear-time algorithm to construct a
rectilinear Steiner minimal tree for
$k$-extremal point sets . . . . . . . . 247--276
Sailesh K. Rao and
P. Sadayappan and
Frank K. Hwang and
Peter W. Shor The Rectilinear Steiner Arborescence
Problem . . . . . . . . . . . . . . . . 277--288
J. Scott Provan Two New Criteria for Finding Steiner
Hulls in Steiner Tree Problems . . . . . 289--302
Charles J. Colbourn A note on bounding $k$-terminal
reliability . . . . . . . . . . . . . . 303--307
Pawel Winter and
J. MacGregor Smith Path-Distance Heuristics for the Steiner
Problem in Undirected Networks . . . . . 309--327
Warren D. Smith and
Peter W. Shor Steiner Tree Problems . . . . . . . . . 329--332
Stefan Voß Problems with Generalized Steiner
Problems . . . . . . . . . . . . . . . . 333--335
Otfried Schwarzkopf Erratum: ``Parallel computation of
distance transforms'' . . . . . . . . . 337
John E. Hopcroft and
Peter J. Kahn A Paradigm for Robust Geometric
Algorithms . . . . . . . . . . . . . . . 339--380
Leonidas J. Guibas and
Donald E. Knuth and
Micha Sharir Randomized Incremental Construction of
Delaunay and Vorono\uì Diagrams . . . . . 381--413
Andrew M. Liao Three Priority Queue Applications
Revisited . . . . . . . . . . . . . . . 415--427
Greg N. Frederickson Editor's Foreword Special Issue on Graph
Algorithms . . . . . . . . . . . . . . . 429--431
Jeffery Westbrook and
Robert Endre Tarjan Maintaining Bridge-Connected and
Biconnected Components On-Line . . . . . 433--464
Harold N. Gabow and
Herbert H. Westermann Forests, Frames, and Games: Algorithms
for Matroid Sums and Applications . . . 465--497
Dan Gusfield and
Charles U. Martel A Fast Algorithm for the Generalized
Parametric Minimum Cut Problem and
Applications . . . . . . . . . . . . . . 499--519
B. Mishra and
Robert Endre Tarjan A Linear-Time Algorithm for Finding an
Ambitus . . . . . . . . . . . . . . . . 521--554
Richard B. Borie and
R. Gary Parker and
Craig A. Tovey Automatic Generation of Linear-Time
Algorithms from Predicate Calculus
Descriptions of Problems on Recursively
Constructed Graph Families . . . . . . . 555--581
Hiroshi Nagamochi and
Toshihide Ibaraki A linear-time algorithm for finding a
sparse $k$-connected spanning subgraph
of a $k$-connected graph . . . . . . . . 583--596
John H. Reif and
Paul G. Spirakis Expected Parallel Time and Sequential
Space Complexity of Graph and Digraph
Problems . . . . . . . . . . . . . . . . 597--630
Joan M. Lucas and
Marian Gunsher Sackrowitz Efficient Parallel Algorithms for Path
Problems in Directed Graphs . . . . . . 631--648
Jacob T. Schwartz and
Micha Sharir Finding effective ``force targets'' for
two-dimensional, multifinger frictional
grips . . . . . . . . . . . . . . . . . 1--20
Sanguthevar Rajasekaran and
Thanasis Tsantilas Optimal Routing Algorithms for
Mesh-Connected Processor Arrays . . . . 21--38
Robert E. Webber and
Hanan Samet Linear-Time Border-Tracing Algorithms
for Quadtrees . . . . . . . . . . . . . 39--54
Joseph S. B. Mitchell $L_1$ Shortest Paths Among Polygonal
Obstacles in the Plane . . . . . . . . . 55--88
Sun Wu and
Udi Manber Path-Matching Problems . . . . . . . . . 89--101
Dan Gusfield and
Leonard Pitt A bounded approximation for the minimum
cost $2$-sat problem . . . . . . . . . . 103--117
Christine Rüb Line-Segment Intersection Reporting in
Parallel . . . . . . . . . . . . . . . . 119--144
Donald Goldfarb and
Jianxiu Hao Polynomial-Time Primal Simplex
Algorithms for the Minimum Cost Network
Flow Problem . . . . . . . . . . . . . . 145--160
Ilan Adler and
Renato D. C. Monteiro A Geometric View of Parametric Linear
Programming . . . . . . . . . . . . . . 161--176
M. S. Chang and
C. Y. Tang and
R. C. T. Lee Solving the Euclidean bottleneck
matching problem by $k$-relative
neighborhood graphs . . . . . . . . . . 177--194
Amy J. Briggs An Efficient Algorithm for One-Step
Planar Compliant Motion Planning with
Uncertainty . . . . . . . . . . . . . . 195--208
Mikhail J. Atallah and
Jyh Jong Tsay On the Parallel-Decomposability of
Geometric Problems . . . . . . . . . . . 209--231
C. K. Cheng and
T. C. Hu Maximum Concurrent Flows and Minimum
Cuts . . . . . . . . . . . . . . . . . . 233--249
Christos Levcopoulos and
Andrzej Lingas There Are Planar Graphs Almost as Good
as the Complete Graphs and Almost as
Cheap as Minimum Spanning Trees . . . . 251--256
Franco P. Preparata and
Jeffrey Scott Vitter and
Mariette Yvinec Output-Sensitive Generation of the
Perspective View of Isothetic
Parallelepipeds . . . . . . . . . . . . 257--283
Alberto Apostolico Optimal Parallel Detection of Squares in
Strings . . . . . . . . . . . . . . . . 285--319
Jean-Daniel Boissonnat and
Mariette Yvinec Probing a Scene of Nonconvex Polyhedra 321--342
Mikhail J. Atallah Editor's Foreword: Special Issue on the
Sixth Annual Symposium on Computational
Geometry . . . . . . . . . . . . . . . . 343--344
Zhenyu Li and
Victor Milenkovic Constructing Strongly Convex Hulls Using
Exact or Rounded Arithmetic . . . . . . 345--364
Rudolf Fleischer and
Kurt Mehlhorn and
Günter Rote and
Emo Welzl and
Chee K. Yap Simultaneous Inner and Outer
Approximation of Shapes . . . . . . . . 365--389
Helmut Alt and
Rudolf Fleischer and
Michael Kaufmann and
Kurt Mehlhorn and
Stefan Näher and
Stefan Schirra and
Christian Uhrig Approximate Motion Planning and the
Complexity of the Boundary of the Union
of Simple Geometric Figures . . . . . . 391--406
Bernard Chazelle and
Micha Sharir and
Emo Welzl Quasi-Optimal Upper Bounds for Simplex
Range Searching and New Zone Theorems 407--429
Joseph S. B. Mitchell and
Günter Rote and
Gerhard J. Woeginger Minimum-Link Paths Among Obstacles in
the Plane . . . . . . . . . . . . . . . 431--459
Michael T. Goodrich and
Steven B. Shauck and
Sumanta Guha Parallel Methods for Visibility and
Shortest-Path Problems in Simple
Polygons . . . . . . . . . . . . . . . . 461--486
R. Z. Hwang and
Richard C. T. Lee and
R. C. Chang The slab dividing approach to solve the
Euclidean $P$-center problem . . . . . . 1--22
Philip N. Klein and
Clifford Stein A Parallel Algorithm for Approximating
the Minimum Cycle Cover . . . . . . . . 23--31
Manfred Kunde Packet Routing on Grids of Processors 32--46
Michael Kaufmann and
F. Miller Maley Parity Conditions in Homotopic
Knock-Knee Routing . . . . . . . . . . . 47--63
Michael J. Todd and
Yu Fei Wang On combined phase $1$--phase $2$
projective methods for linear
programming . . . . . . . . . . . . . . 64--83
Majid Sarrafzadeh and
Ruey-Der Lou Maximum $k$-covering of weighted
transitive graphs with applications . . 84--100
T. Berger and
A. Hekstra and
Alon Orlitsky Asymptotic Component Densities in
Programmable Gate Arrays Realizing All
Circuits of a Given Size . . . . . . . . 101--127
Michael T. Goodrich and
Colm Ó'Dúnlaing and
Chee K. Yap Constructing the Vorono\uì Diagram of a
Set of Line Segments in Parallel . . . . 128--141
Barry Joe and
Cao An Wang Duality of Constrained Vorono\uì Diagrams
and Delaunay Triangulations . . . . . . 142--155
Mikhail J. Atallah A Faster Parallel Algorithm for a Matrix
Searching Problem . . . . . . . . . . . 156--167
Jon Louis Bentley and
Kenneth L. Clarkson and
David B. Levine Fast Linear Expected-Time Algorithms for
Computing Maxima and Convex Hulls . . . 168--183
Robert A. Bosch and
Kurt M. Anstreicher On partial updating in a potential
reduction linear programming algorithm
of Kojima, Mizuno, and Yoshise . . . . . 184--197
P. B. Ramprasad and
C. Pandu Rangan A Linear Algorithm for the
All-Bidirectional-Edges Problem on
Planar Graphs . . . . . . . . . . . . . 199--216
Lin Chen Efficient Parallel Recognition of Some
Circular Arc Graphs, I . . . . . . . . . 217--238
Richard J. Lipton and
Jeffrey F. Naughton Clocked Adversaries for Hashing . . . . 239--252
Edward G. Coffman, Jr. and
Peter W. Shor Packings in Two Dimensions: Asymptotic
Average-Case Analysis of Algorithms . . 253--277
Walter Meyer Seven Fingers Allow Force-Torque Closure
Grasps on Any Convex Polyhedron . . . . 278--292
Richard Anderson and
Simon Kahan and
Martine D. F. Schlag Single-Layer Cylindrical Compaction . . 293--312
Eric Bach and
Jonathan Sorenson Sieve Algorithms for Perfect Power
Testing . . . . . . . . . . . . . . . . 313--328
Jean-Daniel Boissonnat and
Olivier Devillers and
Monique Teillaud A Semidynamic Construction of
Higher-Order Vorono\uì Diagrams and Its
Randomized Analysis . . . . . . . . . . 329--356
Shaunak Pawagi and
Owen Kaser Optimal Parallel Algorithms for Multiple
Updates of Minimum Spanning Trees . . . 357--381
Richard Kenyon Tiling a Polygon with Parallelograms . . 382--397
R. Z. Hwang and
R. C. Chang and
Richard C. T. Lee The Searching over Separators Strategy
To Solve Some NP-Hard Problems in
Subexponential Time . . . . . . . . . . 398--423
M. Y. Chan and
Francis Chin Schedulers for Larger Classes of
Pinwheel Instances . . . . . . . . . . . 425--462
Alexander Z. Zelikovsky An $11/6$-approximation algorithm for
the network Steiner problem . . . . . . 463--470
Marco Pellegrini Ray shooting on triangles in $3$-space 471--494
Pankaj K. Agarwal and
Boris Aronov and
Micha Sharir and
Subhash Suri Selecting Distances in the Plane . . . . 495--514
Michael T. Goodrich and
Steven B. Shauck and
Sumanta Guha An addendum to: ``Parallel methods for
visibility and shortest-path problems in
simple polygons'' . . . . . . . . . . . 515--516
David P. Dobkin and
John Hershberger and
David G. Kirkpatrick and
Subhash Suri Computing the Intersection-Depth of
Polyhedra . . . . . . . . . . . . . . . 518--533
Leonidas J. Guibas and
David Salesin and
Jorge Stolfi Constructing Strongly Convex Approximate
Hulls with Inaccurate Primitives . . . . 534--560
János Pach and
Richard Pollack and
Emo Welzl Weaving Patterns of Lines and Line
Segments in Space . . . . . . . . . . . 561--571
Tetsuo Asano and
Takeshi Tokuyama Algorithms for Projecting Points to Give
the Most Uniform Distribution with
Applications to Hashing . . . . . . . . 572--590
Feng Gao and
Leonidas J. Guibas and
David G. Kirkpatrick and
William T. Laaser and
James B. Saxe Finding Extrema with Unary Predicates 591--600
Kuo-Hui Tsai and
Wen Lian Hsu Fast Algorithms for the Dominating Set
Problem on Permutation Graphs . . . . . 601--614
Tak Wah Lam and
Kwong-fai Chan Finding Least-Weight Subsequences with
Fewer Processors . . . . . . . . . . . . 615--628
Svante Carlsson and
Christos Levcopoulos and
Ola Petersson Sublinear Merging and Natural Mergesort 629--648
Kazumiti Numata and
Takeshi Tokuyama Splitting a Configuration in a Simplex 649--668
David P. Dobkin and
Leonidas J. Guibas and
John Hershberger and
Jack Snoeyink An Efficient Algorithm for Finding the
CSG Representation of a Simple Polygon 1--23
Juraj Hromkovi\vc and
Claus-Dieter Jeschke and
Burkhard Monien Optimal Algorithms for Dissemination of
Information in Some Interconnection
Networks . . . . . . . . . . . . . . . . 24--40
Kikuo Fujimura and
Hanan Samet Planning a Time-Minimal Motion Among
Moving Obstacles . . . . . . . . . . . . 41--63
Dan Gusfield and
Dalit Naor Extracting Maximal Information About
Sets of Minimum Cuts . . . . . . . . . . 64--89
Bruce Randall Donald Special Issue on Computational Robotics:
The Geometric Theory of Manipulation,
Planning, and Control . . . . . . . . . 91--101
John F. Canny and
Ming C. Lin An Opportunistic Global Path Planner . . 102--120
Jérôme Barraquand and
Jean-Claude Latombe Nonholonomic Multibody Mobile Robots:
Controllability and Motion Planning in
the Presence of Obstacles . . . . . . . 121--155
John H. Reif and
Stephen R. Tate Continuous Alternation: The Complexity
of Pursuit in Continuous Domains . . . . 156--181
Christian Icking and
Günter Rote and
Emo Welzl and
Chee K. Yap Shortest Paths for Line Segments . . . . 182--200
Kenneth Y. Goldberg Orienting Polygonal Parts Without
Sensors . . . . . . . . . . . . . . . . 201--225
Michael Erdmann and
Matthew T. Mason and
George Van\ve\vcek, Jr. Mechanical Parts Orienting: The Case of
a Polyhedron on a Table . . . . . . . . 226--247
Michael Erdmann Randomization for Robot Tasks: Using
Dynamic Programming in the Space of
Knowledge States . . . . . . . . . . . . 248--291
David Baraff Issues in Computing Contact Forces for
Non-Penetrating Rigid Bodies . . . . . . 292--352
Esko Ukkonen and
Derick Wood Approximate String Matching with Suffix
Automata . . . . . . . . . . . . . . . . 353--364
Kurt M. Anstreicher and
D. den Hertog and
C. Roos and
T. Terlaky A Long-Step Barrier Method for Convex
Quadratic Programming . . . . . . . . . 365--382
Yossi Malka and
Shlomo Moran and
Shmuel Zaks A Lower Bound on the Period Length of a
Distributed Scheduler . . . . . . . . . 383--398
Esther M. Arkin and
Samir Khuller and
Joseph S. B. Mitchell Geometric Knapsack Problems . . . . . . 399--427
Yachyang Sun and
Majid Sarrafzadeh Floor-planning by Graph Dualization: \sf
L-shaped modules . . . . . . . . . . . . 429--456
Jerzy W. Jaromczyk and
G. W. Wasilkowski Numerical Stability of a Convex Hull
Algorithm for Simple Polygons . . . . . 457--472
Philippe Flajolet and
Gaston H. Gonnet and
Claude Puech and
J. M. Robson Analytic Variations on Quadtrees . . . . 473--500
S. L. Mantzaris Comment on: ``An improved algorithm for
finding the median distributively''
[Algorithmica \bf 2 (1987), no.\ 2,
235--249] by F. Chin and H. F. Ting . . 501--504
Prabhakar Raghavan Guest Editor's Foreword: Special Issue
on On-Line Algorithms . . . . . . . . . 1
Shai Ben-David and
Allan Borodin and
R. Karp and
Gábor Tardos and
Avi Wigderson On the Power of Randomization in On-Line
Algorithms . . . . . . . . . . . . . . . 2--14
Nick Reingold and
Jeffery Westbrook and
Daniel Dominic Sleator Randomized Competitive Algorithms for
the List Update Problem . . . . . . . . 15--32
Marshall W. Bern and
Daniel H. Greene and
Arvind Raghunathan and
Madhu Sudan On-Line Algorithms for Locating
Checkpoints . . . . . . . . . . . . . . 33--52
Sandy Irani Coloring Inductive Graphs On-Line . . . 53--72
Shai Ben-David and
Allan Borodin A New Measure for the Study of On-Line
Algorithms . . . . . . . . . . . . . . . 73--91
Vladimir Batagelj and
Simona Korenjak-\vCerne and
Sandi Klav\vzar Dynamic Programming and Convex
Clustering . . . . . . . . . . . . . . . 93--103
Rudolf Fleischer A tight lower bound for the worst case
of Bottom-Up-Heapsort . . . . . . . . . 104--115
Bernard Chazelle and
Herbert Edelsbrunner and
Leonidas J. Guibas and
Micha Sharir Algorithms for Bichromatic Line-Segment
Problems and Polyhedral Terrains . . . . 116--132
Reuven Bar-Yehuda and
Sergio Fogel Variations on Ray Shooting . . . . . . . 133--145
Johan Jeuring The Derivation of On-Line Algorithms,
with an Application To Finding
Palindromes . . . . . . . . . . . . . . 146--184
Pankaj K. Agarwal and
Micha Sharir Planar Geometric Location Problems . . . 185--195
Harold N. Gabow Editor's Foreword: Special Issur on
Network Flow Algorithms . . . . . . . . 197--199
Samir Khuller and
Joseph Naor Flow in Planar Graphs with Vertex
Capacities . . . . . . . . . . . . . . . 200--225
Tomasz Radzik and
Andrew V. Goldberg Tight Bounds on the Number of
Minimum-Mean Cycle Cancellations and
Related Results . . . . . . . . . . . . 226--242
Kazuo Iwano and
Shinji Misono and
Shu Tezuka and
Satoru Fujishige A New Scaling Algorithm for the Maximum
Mean Cut Problem . . . . . . . . . . . . 243--255
Yaron Pinto and
Ron Shamir Efficient Algorithms for Minimum-Cost
Flow Problems with Piecewise-Linear
Convex Costs . . . . . . . . . . . . . . 256--277
Dan Gusfield and
Éva Tardos A Faster Parametric Minimum-Cut
Algorithm . . . . . . . . . . . . . . . 278--290
Tomás Feder Network flow and $2$-satisfiability . . 291--319
Edith Cohen and
Nimrod Megiddo Algorithms and Complexity Analysis for
Some Flow Problems . . . . . . . . . . . 320--340
Heather Booth and
Jeffery Westbrook A Linear Algorithm for Analysis of
Minimum Spanning and Shortest-Path Trees
of Planar Graphs . . . . . . . . . . . . 341--352
Levent Tunçel On the Complexity of Preflow-Push
Algorithms for Maximum-Flow Problems . . 353--359
Marshall W. Bern and
David P. Dobkin and
David Eppstein and
Robert L. Grossman Visibility with a Moving Point of View 360--378
Peter Eades and
Nicholas C. Wormald Edge Crossings in Drawings of Bipartite
Graphs . . . . . . . . . . . . . . . . . 379--403
Peter Epstein and
J. Kavanagh and
A. Knight and
J. May and
T. Nguyen and
Jörg-Rüdiger Sack A Workbench for Computational Geometry 404--428
Thomas H. Spencer Provably Good Pattern Generators for a
Random Pattern Test . . . . . . . . . . 429--442
Vijaya Ramachandran and
Honghua Yang Finding the Closed Partition of a Planar
Graph . . . . . . . . . . . . . . . . . 443--468
Mark H. Overmars and
Micha Sharir An Improved Technique for
Output-Sensitive Hidden Surface Removal 469--484
Christos H. Papadimitriou and
P. Venkat Rangan and
Martha Sideri Designing Secure Communication Protocols
from Trust Specification . . . . . . . . 485--499
Mordecai J. Golin A Provably Fast Linear-Expected-Time
Maxima-Finding Algorithm . . . . . . . . 501--524
Neal E. Young The $k$-server dual and loose
competitiveness for paging . . . . . . . 525--541
Anna R. Karlin and
Mark S. Manasse and
Lyle A. McGeoch and
Susan S. Owicki Competitive Randomized Algorithms for
Nonuniform Problems . . . . . . . . . . 542--571
Amos Fiat and
Yuval Rabani and
Yiftach Ravid and
Baruch Schieber A Deterministic $O(k^3)$-Competitive
$k$-Server Algorithm for the Circle . . 572--578
Lee R. Nackman and
V. Srinivasan Point Placement Algorithms for Delaunay
Triangulation of Polygonal Domains . . . 1--17
Christian Schwarz and
Michiel H. M. Smid and
Jack Snoeyink An Optimal Algorithm for the On-Line
Closest-Pair Problem . . . . . . . . . . 18--29
Mark de Berg and
Dan Halperin and
Mark H. Overmars and
Jack Snoeyink and
Marc J. van Kreveld Efficient Ray Shooting and Hidden
Surface Removal . . . . . . . . . . . . 30--53
Bernard Chazelle and
Herbert Edelsbrunner and
Michelangelo Grigni and
Leonidas J. Guibas and
John Hershberger and
Micha Sharir and
Jack Snoeyink Ray Shooting in Polygons Using Geodesic
Triangulations . . . . . . . . . . . . . 54--68
Jeffrey Scott Vitter Guest Editor's Introduction: Special
Issue on Large-Scale Memories . . . . . 69--71
Bowen Alpern and
Larry Carter and
Ephraim Feig and
Ted Selker The Uniform Memory Hierarchy Model of
Computation . . . . . . . . . . . . . . 72--109
Jeffrey Scott Vitter and
Elizabeth A. M. Shriver Algorithms for parallel memory. I.
Two-level memories . . . . . . . . . . . 110--147
Jeffrey Scott Vitter and
Elizabeth A. M. Shriver Algorithms for parallel memory. II.
Hierarchical multilevel memories . . . . 148--169
A. Chin Locality-Preserving Hash Functions for
General Purpose Parallel Computation . . 170--181
Lisa Hellerstein and
Garth A. Gibson and
Richard M. Karp and
Randy H. Katz and
David A. Patterson Coding Techniques for Handling Failures
in Large Disk Arrays . . . . . . . . . . 182--208
L. Newberg and
D. Wolfe String Layouts for a Redundant Array of
Inexpensive Disks . . . . . . . . . . . 209--224
Manuel Blum and
William S. Evans and
Peter Gemmell and
Sampath Kannan and
Moni Naor Checking the Correctness of Memories . . 225--244
Alberto Apostolico Guest Editor's Foreword: Special Issue
on String Algorithmics and Its
Applications . . . . . . . . . . . . . . 245--246
Maxime Crochemore and
Artur Czumaj and
Leszek G\kasieniec and
Stefan Jarominek and
Thierry Lecroq and
Wojciech Plandowski and
Wojciech Rytter Speeding Up Two String-Matching
Algorithms . . . . . . . . . . . . . . . 247--267
Ricardo A. Baeza-Yates and
Christian Choffrut and
Gaston H. Gonnet On Boyer--Moore automata . . . . . . . . 268--292
F. Chin and
C. K. Poon Performance Analysis of Some Simple
Heuristics for Computing Longest Common
Subsequences . . . . . . . . . . . . . . 293--311
Dan Gusfield and
K. Balasubramanian and
Dalit Naor Parametric Optimization of Sequence
Alignment . . . . . . . . . . . . . . . 312--326
William I. Chang and
Eugene L. Lawler Sublinear Approximate String Matching
and Biological Applications . . . . . . 327--344
Eugene W. Myers A Sublinear Algorithm for Approximate
Keyword Searching . . . . . . . . . . . 345--374
Gad M. Landau and
Uzi Vishkin Pattern Matching in a Digitized Image 375--408
Aviezri S. Fraenkel and
Shmuel T. Klein Complexity Aspects of Guessing Prefix
Codes . . . . . . . . . . . . . . . . . 409--419
Y. C. Wee and
Seth Chaiken and
S. S. Ravi Rectilinear Steiner Tree Heuristics and
Minimum Spanning Tree Algorithms Using
Geographic Nearest Neighbors . . . . . . 421--435
Ilan Adler and
Peter A. Beling Polynomial Algorithms for Linear
Programming over the Algebraic Numbers 436--457
Pang-Chieh Chen Heuristic Sampling on DAGs . . . . . . . 458--475
Paola Bertolazzi and
Giuseppe Di Battista and
Giuseppe Liotta and
Carlo Mannino Upward Drawings of Triconnected Digraphs 476--497
Gabriele Blankenagel and
Ralf Hartmut Güting External Segment Trees . . . . . . . . . 498--532
Lenwood S. Heath and
Sriram V. Pemmaraju New Results for the Minimum Weight
Triangulation Problem . . . . . . . . . 533--552
Eugene W. Myers Guest Editor's Foreword: Special Issue
on Computational Molecular Biology . . . 1--6
John D. Kececioglu and
Eugene W. Myers Combinatorial Algorithms for DNA
Sequence Assembly . . . . . . . . . . . 7--51
Farid Alizadeh and
Richard M. Karp and
L. A. Newberg and
Deborah K. Weisser Physical Mapping of Chromosomes: A
Combinatorial Problem in Molecular
Biology . . . . . . . . . . . . . . . . 52--76
Pavel A. Pevzner DNA physical mapping and alternating
Eulerian cycles in colored graphs . . . 77--105
Kun-Mao Chao and
Webb Miller Linear-Space Algorithms that Build Local
Alignments from Fragments . . . . . . . 106--134
Pavel A. Pevzner and
M. S. Waterman Multiple Filtration and Approximate
Pattern Matching . . . . . . . . . . . . 135--154
Martin Farach and
Sampath Kannan and
Tandy Warnow A Robust Model for Finding Optimal
Evolutionary Trees . . . . . . . . . . . 155--179
John D. Kececioglu and
David Sankoff Exact and Approximation Algorithms for
Sorting by Reversals, with Application
to Genome Rearrangement . . . . . . . . 180--210
James R. Knight and
Eugene W. Myers Super-Pattern Matching . . . . . . . . . 211--243
Robert F. Cohen and
Roberto Tamassia Dynamic Expression Trees . . . . . . . . 245--265
Michael R. Fellows and
Jan Kratochvíl and
Martin Middendorf and
F. Pfeiffer The Complexity of Induced Minors and
Related Problems . . . . . . . . . . . . 266--282
Keith E. Humenik and
P. Matthews and
A. B. Stephens and
Yelena Yesha A Lower Bound on the Probability of
Conflict Under Nonuniform Access in
Database Systems . . . . . . . . . . . . 283--300
Hans-Peter Lenhof and
Michiel H. M. Smid Maintaining the Visibility Map of
Spheres While Moving the Viewpoint on a
Circle at Infinity . . . . . . . . . . . 301--312
Hosam M. Mahmoud The Joint Distribution of the Three
Types of Nodes in Uniform Binary Trees 313--323
Pankaj K. Agarwal and
Ji\vrí Matou\vsek Dynamic Half-Space Range Reporting and
Its Applications . . . . . . . . . . . . 325--345
Danilo Bruschi and
F. Ravasio Random Parallel Algorithms for Finding
Exact Branchings, Perfect Matchings, and
Cycles . . . . . . . . . . . . . . . . . 346--356
Michael Jünger and
William R. Pulleyblank New Primal and Dual Matching Heuristics 357--380
Ding Zhu Du On Greedy Heuristics for Steiner Minimum
Trees . . . . . . . . . . . . . . . . . 381--386
P. J. de Rezende and
D. T. Lee Point set pattern matching in
$d$-dimensions . . . . . . . . . . . . . 387--404
Maxime Crochemore and
Wojciech Rytter Squares, Cubes, and Time-Space Efficient
String Searching . . . . . . . . . . . . 405--425
Catherine C. McGeoch All-Pairs Shortest Paths and the
Essential Subgraph . . . . . . . . . . . 426--441
D. S. Atkinson and
Pravin M. Vaidya Using Geometry To Solve the
Transportation Problem in the Plane . . 442--461
David Eppstein Asymptotic Speed-Ups in Constructive
Solid Geometry . . . . . . . . . . . . . 462--471
Anthony Lazanas and
Jean-Claude Latombe Landmark-Based Robot Navigation . . . . 472--501
Monika Rauch Henzinger Fully Dynamic Biconnectivity in Graphs 503--538
Achim Schweikard and
R. H. Wilson Assembly Sequences for Polyhedra . . . . 539--552
Xin He An Efficient Parallel Algorithm for
Finding Rectangular Duals of Plane
Triangular Graphs . . . . . . . . . . . 553--572
Michel Habib and
Marianne Huchard and
Jeremy Spinrad A Linear Algorithm To Decompose
Inheritance Graphs Into Modules . . . . 573--591
Pilar de la Torre and
Raymond Greenlaw and
Alejandro A. Schäffer Optimal Edge Ranking of Trees in
Polynomial Time . . . . . . . . . . . . 592--618
Sven Schuierer and
D. Wood Staircase Visibility and Computation of
Kernels . . . . . . . . . . . . . . . . 1--26
Seung-Hak Choi and
Sung Yong Shin and
Kyung-Yong Chwa Characterizing and Recognizing the
Visibility Graph of a Funnel-Shaped
Polygon . . . . . . . . . . . . . . . . 27--51
Bogdan S. Chlebus and
Krzysztof Diks and
Miroslaw Kowaluk $O(\log\log n)$-time integer geometry on
the CRCW PRAM . . . . . . . . . . . . . 52--69
Sally A. Goldman and
Robert H. Sloan Can PAC Learning Algorithms Tolerate
Random Attribute Noise? . . . . . . . . 70--84
James R. Knight and
Eugene W. Myers Approximate Regular Expression Pattern
Matching with Concave Gap Penalties . . 85--121
Richard B. Borie Generation of Polynomial-Time Algorithms
for Some Optimization Problems on
Tree-Decomposable Graphs . . . . . . . . 123--137
L. Cai and
Derek G. Corneil Isomorphic Tree Spanner Problems . . . . 138--153
P. Dietz and
Kurt Mehlhorn and
Rajeev Raman and
Christian Uhrig Lower Bounds for Set Intersection
Queries . . . . . . . . . . . . . . . . 154--168
Nancy M. Amato and
Franco P. Preparata A Time-Optimal Parallel Algorithm for
Three-Dimensional Convex Hulls . . . . . 169--182
Nancy M. Amato Finding a Closest Visible Vertex Pair
Between Two Polygons . . . . . . . . . . 183--201
Shuo-Yan Chou and
R. C. Woo A Linear-Time Algorithm for Constructing
a Circular Visibility Diagram . . . . . 203--228
Ross M. McConnell An $O(n^2)$ Incremental Algorithm for
Modular Decomposition of Graphs and
$2$-Structures . . . . . . . . . . . . . 229--248
Esko Ukkonen On-Line Construction of Suffix Trees . . 249--260
Andrzej Lingas and
Anil Maheshwari and
Jörg-Rüdiger Sack Optimal Parallel Algorithms for
Rectilinear Link-Distance Problems . . . 261--289
Frank Thomson Leighton and
Fillia Makedon and
Ioannis G. Tollis A $2n-2$ Step Algorithm for Routing in
an $n\times n$ Array with Constant-Size
Queues . . . . . . . . . . . . . . . . . 291--304
Samir Khuller and
Balaji Raghavachari and
Neal E. Young Balancing Minimum Spanning Trees and
Shortest-Path Trees . . . . . . . . . . 305--321
Sairam Subramanian and
Roberto Tamassia and
Jeffrey Scott Vitter An Efficient Parallel Algorithm for
Shortest Paths in Planar Layered
Digraphs . . . . . . . . . . . . . . . . 322--339
W. Panny and
Helmut Prodinger Bottom-Up Mergesort---a Detailed
Analysis . . . . . . . . . . . . . . . . 340--354
Dany Breslauer and
Zvi Galil Finding All Periods and Initial
Palindromes of a String in Parallel . . 355--366
Yui-Bin Chen and
Doug J. Ierardi The Complexity of Oblivious Plans for
Orienting and Distinguishing Polygonal
Parts . . . . . . . . . . . . . . . . . 367--397
Ming-Yang Kao and
Shang-Hua Teng and
Kentaro Toyama An Optimal Parallel Algorithm for Planar
Cycle Separators . . . . . . . . . . . . 398--408
Andrew Chi-Chih Yao Minimean Optimal Key Arrangements in
Hash Tables . . . . . . . . . . . . . . 409--428
Mikhail J. Atallah and
Danny Z. Chen and
D. T. Lee An Optimal Algorithm for Shortest Paths
on Weighted Interval and Circular-Arc
Graphs, with Applications . . . . . . . 429--441
Bruce Randall Donald and
Patrick G. Xavier Provably Good Approximation Algorithms
for Optimal Kinodynamic Planning: Robots
with Decoupled Dynamics Bounds . . . . . 443--479
Bruce Randall Donald and
Patrick G. Xavier Provably Good Approximation Algorithms
for Optimal Kinodynamic Planning for
Cartesian Robots and Open-Chain
Manipulators . . . . . . . . . . . . . . 480--530
F. Miller Maley Testing Homotopic Routability Under
Polygonal Wiring Rules . . . . . . . . . 1--16
G. N. Srinivasa Prasanna and
Bruce R. Musicus The Optimal Control Approach to
Generalized Multiprocessor Scheduling 17--49
Sun Wu and
Udi Manber and
Eugene W. Myers A Subquadratic Algorithm for Approximate
Limited Expression Matching . . . . . . 50--67
Shou Wen Tang and
Kaizhong Zhang and
Xiaolin Wu Fast Algorithms for Minimum Matrix Norm
with Application in Computer Graphics 68--81
Michael B. Dillencourt and
Hanan Samet Using Topological Sweep to Extract the
Boundaries of Regions in Maps
Represented by Region Quadtrees . . . . 82--102
Richard Anderson and
Paul Beame and
Erik Brisson Parallel Algorithms for Arrangements . . 104--125
Michael T. Goodrich and
Mujtaba R. Ghouse and
J. Bright Sweep Methods for Parallel Computational
Geometry . . . . . . . . . . . . . . . . 126--153
Roberto Tamassia and
Jeffrey Scott Vitter Optimal Cooperative Search in Fractional
Cascaded Data Structures . . . . . . . . 154--171
David G. Kirkpatrick and
Teresa M. Przytycka Parallel Construction of Binary Trees
with Near Optimal Weighted Path Length 172--192
Björn Lisper Preconditioning Index Set
Transformations for Time-Optimal Affine
Scheduling . . . . . . . . . . . . . . . 193--203
Kaizhong Zhang A Constrained Edit Distance Between
Unordered Labeled Trees . . . . . . . . 205--222
Herbert Edelsbrunner and
Nimish R. Shah Incremental Topological Flipping Works
for Regular Triangulations . . . . . . . 223--241
K. S. Easwarakumar and
S. V. Krishnan and
C. Pandu Rangan and
S. Seshadri Optimal parallel algorithm for finding
$st$-ambitus of a planar biconnected
graph . . . . . . . . . . . . . . . . . 242--255
B. Mishra Bidirectional Edges Problem: Part I---A
Simple Algorithm . . . . . . . . . . . . 256--286
Ronitt Rubinfeld Designing Checkers for Programs that Run
in Parallel . . . . . . . . . . . . . . 287--301
Giuseppe Di Battista and
Roberto Tamassia On-Line Maintenance of Triconnected
Components with SPQR-Trees . . . . . . . 302--318
Danny Krizanc and
Lata Narayanan and
Rajeev Raman Fast Deterministic Selection on
Mesh-Connected Processor Arrays . . . . 319--331
J. L. Nazareth The Implementation of Linear Programming
Algorithms Based on Homotopies . . . . . 332--350
J. Scott Provan and
D. R. Shier A paradigm for listing $(s,t)$-cuts in
graphs . . . . . . . . . . . . . . . . . 351--372
Konstantinos Kalpakis and
Y. Yesha Scheduling Tree DAGs on Parallel
Architectures . . . . . . . . . . . . . 373--396
Egon Balas and
Jue Xue Weighted and Unweighted Maximum Clique
Algorithms with Upper Bounds from
Fractional Coloring . . . . . . . . . . 397--412
Friedhelm Meyer auf der Heide and
Brigitte Oesterdiekhoff and
Rolf Wanka Strongly Adaptive Token Distribution . . 413--427
Bernard Chazelle and
Herbert Edelsbrunner and
Leonidas J. Guibas and
Micha Sharir and
Jorge Stolfi Lines in Space: Combinatorics and
Algorithms . . . . . . . . . . . . . . . 428--447
Greg N. Frederickson Searching Among Intervals and Compact
Routing Tables . . . . . . . . . . . . . 448--466
Renzo Sprugnoli Recurrence Relations on Heaps . . . . . 467--480
Alberto Apostolico and
Franco P. Preparata Data Structures and Algorithms for the
String Statistics Problem . . . . . . . 481--494
Ruth Kuchem and
Dorothea Wagner and
Frank Wagner Optimizing Area for Three-Layer
Knock-Knee Channel Routing . . . . . . . 495--519
Joseph Cheriyan and
Kurt Mehlhorn Algorithms for Dense Graphs and Networks
on the Random Access Computer . . . . . 521--549
Peichen Pan and
Weiping Shi and
C. L. Liu Area Minimization for Hierarchical
Floorplans . . . . . . . . . . . . . . . 550--571
Yang Cai and
M. C. Kong Nonpreemptive Scheduling of Periodic
Tasks in Uni- and Multiprocessor Systems 572--599
Sanjoy K. Baruah and
N. K. Cohen and
C. Greg Plaxton and
Donald A. Varvel Proportionate Progress: A Notion of
Fairness in Resource Allocation . . . . 600--625
Pankaj K. Agarwal and
Marc J. van Kreveld Connected Component and Simple Polygon
Intersection Searching . . . . . . . . . 626--660
Giuseppe Di Battista and
Roberto Tamassia Guest Editors' Introduction to the
Special Issue on Graph Drwaing . . . . . 1--3
Goos Kant Drawing Planar Graphs Using the
Canonical Ordering . . . . . . . . . . . 4--32
Michael Jünger and
Petra Mutzel Maximum Planar Subgraphs and Nice
Embeddings: Practical Layout Tools . . . 33--59
Peter Eades and
Sue Whitesides The Realization Problem for Euclidean
Minimum Spanning Trees is NP-Hard . . . 60--82
Prosenjit Bose and
William Lenhart and
Giuseppe Liotta Characterizing Proximity Trees . . . . . 83--110
János Pach and
Farhad Shahrokhi and
Mario Szegedy Applications of the Crossing Number . . 111--117
Farhad Shahrokhi and
László A. Székely and
Ondrej Sýkora and
Imrich Vr\softto Drawings of Graphs on Surfaces with Few
Crossings . . . . . . . . . . . . . . . 118--131
Xiaotie Deng and
Christos H. Papadimitriou Competitive Distributed Decision-Making 133--150
J. Ian Munro and
Venkatesh Raman Fast Stable In-Place Sorting with $O(n)$
Data Moves . . . . . . . . . . . . . . . 151--160
Shou-Hsuan Stephen Huang and
Hongfei Liu and
Rakesh M. Verma A New Combinatorial Approach to Optimal
Embeddings of Rectangles . . . . . . . . 161--180
Mark H. Nodine and
Michael T. Goodrich and
Jeffrey Scott Vitter Blocking for External Graph Searching 181--214
David M. Choy and
Ronald Fagin and
Larry J. Stockmeyer Efficiently Extendible Mappings for
Balanced Data Distribution . . . . . . . 215--232
Kurt Mehlhorn and
Petra Mutzel On the Embedding Phase of the Hopcroft
and Tarjan Planarity Testing Algorithm 233--242
Sivaprakasam Sunder and
Xin He An NC algorithm for finding a minimum
weighted completion time schedule on
series parallel graphs . . . . . . . . . 243--262
Dora Giammarresi and
Giuseppe F. Italiano Decremental $2$- and $3$-connectivity on
planar graphs . . . . . . . . . . . . . 263--287
Costas S. Iliopoulos and
D. W. G. Moore and
Kunsoo Park Covering a String . . . . . . . . . . . 288--297
Andris Ambainis Communication complexity in a
$3$-computer model . . . . . . . . . . . 298--301
Lusheng Wang and
Tao Jiang and
Eugene L. Lawler Approximation Algorithms for Tree
Alignment with a Given Phylogeny . . . . 302--315
Masato Edahiro Equispreading Tree in Manhattan Distance 316--338
Jun-ya Takahashi and
Hitoshi Suzuki and
Takao Nishizeki Shortest Noncrossing Paths in Plane
Graphs . . . . . . . . . . . . . . . . . 339--357
Michael Luby Introduction to Special Issue on
Randomized and Derandomized Algorithms 359--366
David Zuckerman Simulating BPP Using a General Weak
Random Source . . . . . . . . . . . . . 367--391
Mark Jerrum and
Umesh V. Vazirani A Mildly Exponential Approximation
Algorithm for the Permanent . . . . . . 392--401
Milena Mihail and
Peter Winkler On the Number of Eulerian Orientations
of a Graph . . . . . . . . . . . . . . . 402--414
Michael Luby and
Boban Veli\vckovi\'c On Deterministic Approximation of DNF 415--433
Noga Alon and
Moni Naor Derandomization, Witnesses for Boolean
Matrix Multiplication and Construction
of Perfect Hash Functions . . . . . . . 434--449
Ketan Mulmuley Randomized Geometric Algorithms and
Pseudorandom Generators . . . . . . . . 450--463
Raimund Seidel and
Cecilia R. Aragon Randomized Search Trees . . . . . . . . 464--497
Ji\vrí Matou\vsek and
Micha Sharir and
Emo Welzl A Subexponential Bound for Linear
Programming . . . . . . . . . . . . . . 498--516
Richard M. Karp and
Michael Luby and
Friedhelm Meyer auf der Heide Efficient PRAM Simulation on a
Distributed Memory Machine . . . . . . . 517--542
Helmut Alt and
Leonidas J. Guibas and
Kurt Mehlhorn and
Richard M. Karp and
Avi Wigderson A Method for Obtaining Randomized
Algorithms with Small Tail Probabilities 543--547
Michele Flammini and
Giorgio Gambosi and
Sandro Salomone Interval Routing Schemes . . . . . . . . 549--568
Richard Cole and
Michael T. Goodrich and
Colm Ó'Dúnlaing A Nearly Optimal Deterministic Parallel
Vorono\uì Diagram Algorithm . . . . . . . 569--617
David Avis Generating Rooted Triangulations Without
Repetitions . . . . . . . . . . . . . . 618--632
Donald B. Johnson and
Panagiotis Takis Metaxas Optimal Algorithms for the Single and
Multiple Vertex Updating Problems of a
Minimum Spanning Tree . . . . . . . . . 633--648
Mark Allen Weiss Shellsort with a Constant Number of
Increments . . . . . . . . . . . . . . . 649--654
Theodore H. Romer and
Louis E. Rosier An Algorithm Reminiscent of
Euclidean-gcd for Computing a Function
Related to Pinwheel Scheduling . . . . . 1--10
Brandon Dixon and
Robert Endre Tarjan Optimal Parallel Verification of Minimum
Spanning Trees in Logarithmic Time . . . 11--18
Frank K. H. A. Dehne and
Rolf Klein ``The Big Sweep'': On the Power of the
Wavefront Approach to Vorono\uì Diagrams 19--32
Sunil Arya and
Michiel H. M. Smid Efficient Construction of a
Bounded-Degree Spanner with Low Weight 33--54
Torben Hagerup and
Miroslaw Kuty\lowski Fast integer merging on the EREW PRAM 55--66
Jòrgen Bang-Jensen and
M. El Haddad and
Yannis Manoussakis and
Teresa M. Przytycka Parallel Algorithms for the Hamiltonian
Cycle and Hamiltonian Path Problems in
Semicomplete Bipartite Digraphs . . . . 67--87
Ronald I. Greenberg and
Jau-Der Shih Minimizing Channel Density with Movable
Terminals . . . . . . . . . . . . . . . 89--99
F. Granot and
J. Skorin-Kapov and
Amir Tamir Using Quadratic Programming to Solve
High Multiplicity Scheduling Problems on
Parallel Machines . . . . . . . . . . . 100--110
Francis Avnaim and
Jean-Daniel Boissonnat and
Olivier Devillers and
Franco P. Preparata and
Mariette Yvinec Evaluating Signs of Determinants Using
Single-Precision Arithmetic . . . . . . 111--132
Jay N. Bhuyan and
Jitender S. Deogun and
Vijay V. Raghavan Algorithms for the Boundary Selection
Problem . . . . . . . . . . . . . . . . 133--161
Laurent Alonso and
Jean-Luc Rémy and
René Schott A Linear-Time Algorithm for the
Generation of Trees . . . . . . . . . . 162--183
Kurt Mehlhorn and
R. Sundar and
Christian Uhrig Maintaining Dynamic Sequences under
Equality Tests in Polylogarithmic Time 183--198
Robert F. Cohen and
Peter Eades and
Tao Lin and
Frank Ruskey Three-Dimensional Graph Drawing . . . . 199--208
Noga Alon and
Raphy Yuster and
Uri Zwick Finding and Counting Given Length Cycles 209--223
Michael Kaufmann and
Jop F. Sibeyn Randomized Multipacket Routing and
Sorting on Meshes . . . . . . . . . . . 224--244
Bernard Chazelle and
Leonidas Palios Decomposing the Boundary of a Nonconvex
Polyhedron . . . . . . . . . . . . . . . 245--265
Lin Chen Efficient Parallel Recognition of Some
Circular Arc Graphs, II . . . . . . . . 266--280
S. Guha and
I. Suzuki Proximity Problems for Points on a
Rectilinear Plane with Rectangular
Obstacles . . . . . . . . . . . . . . . 281--307
Rida A. Bazzi and
Gil Neiger The Complexity of Almost-Optimal
Simultaneous Coordination . . . . . . . 308--321
Rephael Wenger Randomized Quickhull . . . . . . . . . . 322--329
Piotr Berman and
Bhaskar Dasgupta Complexities of Efficient Solutions of
Rectilinear Polygon Cover Problems . . . 331--356
E. Rimon Construction of $C$-space roadmaps from
local sensory data. What should the
sensors look for? . . . . . . . . . . . 357--379
Marco Pellegrini On Counting Pairs of Intersecting
Segments and Off-Line Triangle Range
Searching . . . . . . . . . . . . . . . 380--398
Yijie Han and
Victor Y. Pan and
John H. Reif Efficient Parallel Algorithms for
Computing All Pair Shortest Paths in
Directed Graphs . . . . . . . . . . . . 399--415
Sergio De Agostino and
Rossella Petreschi and
Andrea Sterbini An $O(n^3)$ Recognition Algorithm for
Bithreshold Graphs . . . . . . . . . . . 416--425
Susanne E. Hambrusch and
Hung-Yi Tu New Algorithms for Minimizing the
Longest Wire Length During Circuit
Compaction . . . . . . . . . . . . . . . 426--448
Noga Alon and
Aravind Srinivasan Improved Parallel Approximation of a
Class of Integer Programming Problems 449--462
Anonymous Guest Editor's Foreword . . . . . . . . 1--2
Naveen Garg and
Vijay V. Vazirani and
Mihalis Yannakakis Primal---Dual Approximation Algorithms
for Integral Flow and Multicut in Trees 3--20
R. Ravi and
David P. Williamson An Approximation Algorithm for
Minimum-Cost Vertex-Connectivity
Problems . . . . . . . . . . . . . . . . 21--43
David Peleg and
Gideon Schechtman and
Avishai Wool Randomized Approximation of Bounded
Multicovering Problems . . . . . . . . . 44--66
Alan M. Frieze and
Mark Jerrum Improved approximation algorithms for
MAX $k$-CUT and MAX BISECTION . . . . . 67--81
David R. Karger and
Rajeev Motwani and
G. D. S. Ramkumar On Approximating the Longest Path in a
Graph . . . . . . . . . . . . . . . . . 82--98
Alexander Zelikovsky A Series of Approximation Algorithms for
the Acyclic Directed Steiner Tree
Problem . . . . . . . . . . . . . . . . 99--110
Naveen Garg and
Dorit S. Hochbaum An $O(\log k)$-approximation algorithm
for the $k$ minimum spanning tree
problem in the plane . . . . . . . . . . 111--121
F. K. Miyazawa and
Y. Wakabayashi An Algorithm for the Three-Dimensional
Packing Problem with Asymptotic
Performance Analysis . . . . . . . . . . 122--144
Magnús M. Halldórsson and
Jaikumar Radhakrishnan Greed is Good: Approximating Independent
Sets in Sparse and Bounded-Degree Graphs 145--163
Yui-Bin Chen and
Doug Ierardi Time-Optimal Trajectories of a Rod in
the Plane Subject to Velocity
Constraints . . . . . . . . . . . . . . 165--197
Kuo-Hui H. Tsai and
D. T. Lee $k$ best cuts for circular-arc graphs 198--216
L. Paul Chew and
Steven Fortune Sorting Helps for Vorono\uì Diagrams . . 217--228
Takeshi Tokuyama Orthogonal Queries in Segments . . . . . 229--245
Mark H. Overmars and
Nicola Santoro Improved Bounds for Electing a Leader in
a Synchronous Ring . . . . . . . . . . . 246--262
Valerie King A Simpler Minimum Spanning Tree
Verification Algorithm . . . . . . . . . 263--270
S. V. Rice and
H. Bunke and
T. A. Nartker Classes of Cost Functions for String
Edit Distance . . . . . . . . . . . . . 271--280
T. Lengauer Foreword . . . . . . . . . . . . . . . . 281--282
Susanne Albers On the Influence of Lookahead in
Competitive Paging Algorithms . . . . . 283--305
Mark de Berg and
Marc J. van Kreveld Trekking in the Alps Without Freezing or
Getting Tired . . . . . . . . . . . . . 306--323
Robert F. Cohen and
Roberto Tamassia Combine and Conquer . . . . . . . . . . 324--362
Karsten Weihe Multicommodity Flows in Even, Planar
Networks . . . . . . . . . . . . . . . . 363--383
Vijaya Ramachandran and
Honghua Yang An Efficient Parallel Algorithm for the
Layered Planar Monotone Circuit Value
Problem . . . . . . . . . . . . . . . . 384--404
Ornan Gerstel and
Shmuel Zaks The Bit Complexity of Distributed
Sorting . . . . . . . . . . . . . . . . 405--416
Michael Kaufmann and
Rajeev Raman and
Jop F. Sibeyn Routing on Meshes with Buses . . . . . . 417--444
Ernst W. Mayr and
Ralph Werchner Optimal Tree Contraction and Term
Matching on the Hypercube and Related
Networks . . . . . . . . . . . . . . . . 445--460
William R. Burley and
Sandy Irani On Algorithm Design for Metrical Task
Systems . . . . . . . . . . . . . . . . 461--485
Shlomi Dolev and
Jennifer L. Welch Wait-Free Clock Synchronization . . . . 486--511
S. Muthukrishnan Detecting False Matches in
String-Matching Algorithms . . . . . . . 512--520
Robert Beals Equivalence of Binary and Ternary
Algebraic Decision Trees . . . . . . . . 521--523
S. N. Bespamyatnikh On Constructing Minimum Spanning Trees
in $R^k_l$ . . . . . . . . . . . . . . . 524--529
T. Matsui A Flexible Algorithm for Generating All
the Spanning Trees in Undirected Graphs 530--543
Celina Imieli\'nska and
Bahman Kalantari A General Class of Heuristics for
Minimum Weight Perfect Matching and Fast
Special Cases with Doubly and Triply
Logarithmic Errors . . . . . . . . . . . 544--559
Peichen Pan and
Sai-keung Dong and
C. L. Liu Optimal Graph Constraint Reduction for
Symbolic Layout Compaction . . . . . . . 560--574
J. S. B. Mitchell Guest Editor's Introduction . . . . . . 1--3
David Baraff and
R. Mattikalli and
P. Khosla Minimal Fixturing of Frictionless
Assemblies: Complexity and Algorithms 4--39
A. S. Wallack and
John F. Canny Planning for Modular and Hybrid Fixtures 40--60
Boudewijn Asberg and
Gregoria Blanco and
Prosenjit Bose and
Jesus Garcia-Lopez and
Mark H. Overmars and
Godfried T. Toussaint and
Gordon T. Wilfong and
Binhai Zhu Feasibility of Design in
Stereolithography . . . . . . . . . . . 61--83
Prosenjit Bose and
David Bremner and
Marc J. van Kreveld Determining the Castability of Simple
Polyhedra . . . . . . . . . . . . . . . 84--113
M. S. Karasick and
D. Lieber and
Lee R. Nackman and
V. T. Rajan Visualization of Three-Dimensional
Delaunay Meshes . . . . . . . . . . . . 114--128
Daniela Rus Coordinated Manipulation of Objects in a
Plane . . . . . . . . . . . . . . . . . 129--147
Karen Daniels and
Victor J. Milenkovic Multiple Translational Containment. Part
I: An Approximate Algorithm . . . . . . 148--182
Victor Milenkovic Multiple Translational Containment. Part
II: Exact Algorithms . . . . . . . . . . 183--218
Ioannis Z. Emiris and
John F. Canny and
Raimund Seidel Efficient Perturbations for Handling
Geometric Degeneracies . . . . . . . . . 219--242
Chandrajit L. Bajaj and
Fausto Bernardini and
Guoliang Xu Reconstructing Surfaces and Functions on
Surfaces from Unorganized
Three-Dimensional Data . . . . . . . . . 243--261
Martin L. Brady and
Donna J. Brown and
K. D. Powers Hexagonal Models for Channel Routing . . 263--290
Alok Aggarwal and
Dina Kravets and
James K. Park and
S. Sen Parallel Searching in Generalized Monge
Arrays . . . . . . . . . . . . . . . . . 291--317
J. F. Weng Expansion of Linear Steiner Trees . . . 318--330
Robert Giegerich and
Stefan Kurtz From Ukkonen to McCreight and Weiner: a
unifying view of linear-time suffix tree
construction . . . . . . . . . . . . . . 331--353
Zhi-Zhong Chen and
Xin He Parallel Algorithms for Maximal Acyclic
Sets . . . . . . . . . . . . . . . . . . 354--368
Gary L. Miller and
Shang-Hua Teng Tree-Based Parallel Algorithm Design . . 369--389
Boris V. Cherkassky and
Andrew V. Goldberg On Implementing the Push---Relabel
Method for the Maximum Flow Problem . . 390--410
Shun-Shii Lin and
Kwei-Jay Lin A Pinwheel Scheduler for Three Distinct
Numbers with a Tight Schedulability
Bound . . . . . . . . . . . . . . . . . 411--426
Therese C. Biedl and
Goos Kant and
Michael Kaufmann On Triangulating Planar Graphs Under the
Four-Connectivity Constraint . . . . . . 427--446
Gautam Das and
Sanjiv Kapoor and
Michiel H. M. Smid On the Complexity of Approximating
Euclidean Traveling Salesman Tours and
Minimum Spanning Trees . . . . . . . . . 447--462
Anne Condon and
Lata Narayanan Upper and Lower Bounds for Selection in
the Mesh . . . . . . . . . . . . . . . . 1--30
David Alberts and
Monika Rauch Henzinger Average-Case Analysis of Dynamic Graph
Algorithms . . . . . . . . . . . . . . . 31--60
Franz Aurenhammer and
F. Hoffmann and
Boris Aronov Minkowski-Type Theorems and
Least-Squares Clustering . . . . . . . . 61--76
Nader H. Bshouty and
Christino Tamon and
David K. Wilson On Learning Decision Trees with Large
Output Domains . . . . . . . . . . . . . 77--100
Joseph Y.-T.-T. Leung and
Tommy W. Tam and
C. S. Wong and
Gilbert H. Young Minimizing Mean Flow Time with Error
Constraint . . . . . . . . . . . . . . . 101--118
David Harel and
Meir Sardas An Algorithm for Straight-Line Drawing
of Planar Graphs . . . . . . . . . . . . 119--135
Ji\vrí Matou\vsek and
David M. Mount and
Nathan S. Netanyahu Efficient Randomized Algorithms for the
Repeated Median Line Estimator . . . . . 136--150
Guy Even and
Joseph Naor and
Baruch Schieber and
Madhu Sudan Approximating Minimum Feedback Sets and
Multicuts in Directed Graphs . . . . . . 151--174
Eric Torng A Unified Analysis of Paging and Caching 175--200
Dae Seoung Kim and
Kwan-Hee Yoo and
Kyung-Yong Chwa and
Sung Yong Shin Efficient Algorithms for Computing a
Complete Visibility Region in
Three-Dimensional Space . . . . . . . . 201--225
Kwan-Hee Yoo and
Dae Seoung Kim and
Sung Yong Shin and
Kyung-Yong Chwa Linear-Time Algorithms for Finding the
Shadow Volumes from a Convex Area Light
Source . . . . . . . . . . . . . . . . . 227--241
Yefim Dinitz and
Jeffery Westbrook Maintaining the classes of
$4$-edge-connectivity in a graph on-line 242--276
A. Gräf and
M. Stumpf and
G. Weißenfels On Coloring Unit Disk Graphs . . . . . . 277--293
Siu-Wing Cheng and
Michael Kaminski and
Shmuel Zaks Minimum Dominating Sets of Intervals on
Lines . . . . . . . . . . . . . . . . . 294--308
Tadao Takaoka Subcubic Cost Algorithms for the All
Pairs Shortest Path Problem . . . . . . 309--318
Evanthia Papadopoulou and
D. T. Lee A New Approach for the Geodesic Vorono\uì
Diagram of Points in a Simple Polygon
and Other Restricted Polygonal Domains 319--352
Maxime Crochemore and
Costas S. Iliopoulos and
M. Korda Two-Dimensional Prefix String Matching
and Covering on Square Matrices . . . . 353--373
Sudipto Guha and
Samir Khuller Approximation Algorithms for Connected
Dominating Sets . . . . . . . . . . . . 374--387
Martin Farach and
Mikkel Thorup String Matching in Lempel---Ziv
Compressed Strings . . . . . . . . . . . 388--404
Artur Czumaj and
Przemys\lawa Kanarek and
Miros\law Kuty\lowski and
Krzysztof Lory\'s Fast Generation of Random Permutations
Via Networks Simulation . . . . . . . . 2--20
Alan M. Frieze and
Wojciech Szpankowski Greedy Algorithms for the Shortest
Common Superstring That Are
Asymptotically Optimal . . . . . . . . . 21--36
Alfredo Viola and
Patricio V. Poblete The Analysis of Linear Probing Hashing
with Buckets . . . . . . . . . . . . . . 37--71
Luca Trevisan Parallel Approximation Algorithms by
Positive Linear Programming . . . . . . 72--88
Helmut Alt and
Ulrich Fuchs and
Günter Rote and
Gerald Weber Matching Convex Shapes with Respect to
the Symmetric Difference . . . . . . . . 89--103
Noga Alon and
Yossi Azar and
János Csirik and
Leah Epstein and
Sergey V. Sevastianov and
Arjen P. A. Vestjens and
Gerhard J. Woeginger On-Line and Off-Line Approximation
Algorithms for Vector Covering Problems 104--118
Esther M. Arkin and
Yi-Jen Chiang and
Martin Held and
Joseph S. B. Mitchell and
Vera Sacristan and
Steven Skiena and
Tae-Heng Yang On Minimum-Area Hulls . . . . . . . . . 119--136
Juha Kärkkäinen and
Erkki Sutinen Lempel--Ziv index for $q$-grams . . . . 137--154
J. Díaz and
M. J. Serna Introduction . . . . . . . . . . . . . . ??
Pierre Fraigniaud and
Cyril Gavoille Interval Routing Schemes . . . . . . . . 155--182
Arvind Gupta and
Naomi Nishimura Finding Largest Subtrees and Smallest
Supertrees . . . . . . . . . . . . . . . 183--210
Liang-Fang Chao and
Andrea S. LaPaugh Finding All Minimal Shapes in a Routing
Channel . . . . . . . . . . . . . . . . 211--244
Steven J. Phillips and
Jeffery Westbrook On-Line Load Balancing and Network Flow 245--261
Tao Jiang and
Richard M. Karp Mapping Clones with a Given Ordering or
Interleaving . . . . . . . . . . . . . . 262--284
Christos Levcopoulos and
Drago Krznaric A Linear-Time Approximation Scheme for
Minimum, Weight Triangulation of Convex
Polygons . . . . . . . . . . . . . . . . 285--311
Susanne Albers and
Michael Mitzenmacher Average Case Analyses of List Update
Algorithms, with Applications to Data
Compression . . . . . . . . . . . . . . 312--329
J. Friedman Computing Betti Numbers via
Combinatorial Laplacians . . . . . . . . 331--346
Ishai Ben-Aroya and
Donald D. Chinn and
Assaf Schuster A Lower Bound for Nearly Minimal
Adaptive and Hot Potato Algorithms . . . 347--376
Sanjeev Khanna and
Rajeev Motwani and
Randall H. Wilson On Certificates and Lookahead in Dynamic
Graph Problems . . . . . . . . . . . . . 377--394
Ka Wong Chong and
Tak Wah Lam Approximating Biconnectivity in Parallel 395--410
P. Auer and
W. Maass Introduction . . . . . . . . . . . . . . 1--2
Shai Ben-David Can Finite Samples Detect Singularities
of Real-Valued Functions? . . . . . . . 3--17
Douglas A. Cenzer and
William R. Moser A Good Oracle Is Hard to Beat . . . . . 18--34
Avrim Blum and
Alan M. Frieze and
Ravi Kannan and
Santosh Vempala A Polynomial-Time Algorithm for Learning
Noisy Linear Threshold Functions . . . . 35--52
Stephen Kwek and
Leonard Pitt PAC learning intersections of halfspaces
with membership queries . . . . . . . . 53--75
Amos Beimel and
Eyal Kushilevitz Learning Boxes in High Dimension . . . . 76--90
Nader H. Bshouty and
Christino Tamon and
David K. Wilson Learning Matrix Functions over Rings . . 91--111
Nicol\`o Cesa-Bianchi and
David P. Helmbold and
Sandra Panizza On Bayes Methods for On-Line Boolean
Prediction . . . . . . . . . . . . . . . 112--137
K. Hiraoka and
S. Amari Strategy Under the Unknown Stochastic
Environment: the Nonparametric
Lob---Pass Problem . . . . . . . . . . . 138--156
John Shawe-Taylor Classification Accuracy Based on
Observed Margin . . . . . . . . . . . . 157--172
R. Kamimura Minimizing $f$-Information for
Generalization and Interpretation . . . 173--197
S. M. Rüger A Class of Asymptotically Stable
Algorithms for Lea rning-Rate Adaptation 198--210
Alex J. Smola and
Bernhard Schölkopf On a Kernel-Based Method for Pattern
Recognition, Regression, Approximation,
and Operator Inversion . . . . . . . . . 211--231
D. Eppstein Guest Editor's Foreword . . . . . . . . 233--234
Philip N. Klein and
Sairam Subramanian A Fully Dynamic Approximation Scheme for
Shortest Paths in Planar Graphs . . . . 235--249
Daniele Frigioni and
Alberto Marchetti-Spaccamela and
Umberto Nanni Semidynamic Algorithms for Maintaining
Single-Source Shortest Path Trees . . . 250--274
Giuseppe F. Italiano and
Rajiv Ramaswami Maintaining Spanning Trees of Small
Diameter . . . . . . . . . . . . . . . . 275--304
Bala Swaminathan and
Kenneth J. Goldman An Incremental Distributed Algorithm for
Computing Biconnected Components in
Dynamic Graphs . . . . . . . . . . . . . 305--329
Greg N. Frederickson Maintaining regular properties
dynamically in $k$-terminal graphs . . . 330--350
Monika Rauch Henzinger and
Michael L. Fredman Lower Bounds for Fully Dynamic
Connectivity Problems in Graphs . . . . 351--362
H. Prodinger Preface . . . . . . . . . . . . . . . . 363--365
Helmut Prodinger and
Wojciech Szpankowski Philippe Flajolet's Research in Analysis
of Algorithms and Combinatorics . . . . 366--387
David Aldous A Metropolis-Type Optimization Algorithm
on the Infinite Tree . . . . . . . . . . 388--412
F. T. Bruss and
Michael Drmota and
Guy Louchard The Complete Solution of the Competitive
Rank Selection Problem . . . . . . . . . 413--447
Edward G. Coffman, Jr. and
Leopold Flatto and
P. Jelenkovi\'c and
Bjorn Poonen Packing Random Intervals On-Line . . . . 448--476
Luc Devroye and
Ernst P. Mücke and
Binhai Zhu A Note on Point Location in Delaunay
Triangulations of Random Points . . . . 477--482
Wenceslas Fernandez de la Vega and
Alan M. Frieze and
Miklos Santha Average-case analysis of the merging
algorithm of Hwang and Lin . . . . . . . 483--489
Philippe Flajolet and
Patricio V. Poblete and
Alfredo Viola On the Analysis of Linear Probing
Hashing . . . . . . . . . . . . . . . . 490--515
Micha Hofri and
Philippe Jacquet Saddle Points in Random Matrices:
Analysis of Knuth Search Algorithms . . 516--528
Hsien-Kuei Hwang Asymptotics of Divide-and-Conquer
Recurrences: Batcher's Sorting Algorithm
and a Minimum Euclidean Matching
Heuristic . . . . . . . . . . . . . . . 529--546
Charles Knessl A Note on the Asymptotic Behavior of the
Depth of Tries . . . . . . . . . . . . . 547--560
Donald E. Knuth Linear Probing and Graphs . . . . . . . 561--568
Hosam M. Mahmoud and
Robert T. Smythe Probabilistic analysis of Multiple Quick
Select . . . . . . . . . . . . . . . . . 569--584
Donatella Merlini and
Renzo Sprugnoli and
M. Cecilia Verri Average-Case Analysis for a Simple
Compression Algorithm . . . . . . . . . 585--599
Alois Panholzer and
Helmut Prodinger Average-Case Analysis of Priority Trees:
A Structure for Priority Queue
Administration . . . . . . . . . . . . . 600--630
Mireille Régnier and
Wojciech Szpankowski On Pattern Frequency Occurrences in a
Markovian Sequence . . . . . . . . . . . 631--649
Hadas Shachnai and
Micha Hofri The List Update Problem: Improved Bounds
for the Counter Scheme . . . . . . . . . 650--659
Brigitte Vallée Dynamics of the Binary Euclidean
Algorithm: Functional Analysis and
Operators . . . . . . . . . . . . . . . 660--685
Dennis Moore and
W. F. Smyth and
D. Miller Counting Distinct Strings . . . . . . . 1--13
Xiaotie Deng and
Elias Koutsoupias and
Philip D. MacKenzie Competitive Implementation of Parallel
Programs . . . . . . . . . . . . . . . . 14--30
P. Krishnan and
Philip M. Long and
Jeffrey Scott Vitter Adaptive Disk Spindown via Optimal
Rent-to-Buy in Probabilistic
Environments . . . . . . . . . . . . . . 31--56
Hristo N. Djidjev and
John R. Gilbert Separators in Graphs with Negative and
Multiple Vertex Weights . . . . . . . . 57--71
Lata Narayanan and
Jaroslav Opatrny Compact routing on chordal rings of
degree $4$ . . . . . . . . . . . . . . . 72--96
Luc Devroye A Note on the Expected Time for Finding
Maxima by List Algorithms . . . . . . . 97--108
S. Nicoloso and
Majid Sarrafzadeh and
X. Song On the Sum Coloring Problem on Interval
Graphs . . . . . . . . . . . . . . . . . 109--126
Ricardo A. Baeza-Yates and
Gonzalo Navarro Faster Approximate String Matching . . . 127--158
Konstantinos Kalpakis and
Yaacov Yesha Upper and Lower Bounds on the Makespan
of Schedules for Tree Dags on Linear
Arrays . . . . . . . . . . . . . . . . . 159--179
Marek Chrobak and
John Noga LRU is better than FIFO . . . . . . . . 180--185
Amir H. Farrahi and
D.-T. T. Lee and
Majid Sarrafzadeh Two-Way and Multiway Partitioning of a
Set of Intervals for Clique-Width
Maximization . . . . . . . . . . . . . . 187--210
Panos M. Pardalos and
G. Xue Algorithms for a Class of Isotonic
Regression Problems . . . . . . . . . . 211--222
Vincenzo Auletta and
Angelo Monti and
Mimmo Parente and
Pino Persiano A Linear-Time Algorithm for the
Feasibility of Pebble Motion on Trees 223--245
Arne Andersson and
N. Jesper Larsson and
Kurt Swanson Suffix Trees on Words . . . . . . . . . 246--260
G. Ramalingam and
J. Song and
Leo Joskowicz and
R. E. Miller Solving Systems of Difference
Constraints Incrementally . . . . . . . 261--275
Jin-yi Cai and
C. K. Wong Foreword . . . . . . . . . . . . . . . . 277
Matthew Andrews and
Michel X. Goemans and
Lisa Zhang Improved Bounds for On-Line Load
Balancing . . . . . . . . . . . . . . . 278--301
Giuseppe Di Battista and
Roberto Tamassia and
Luca Vismara Output-Sensitive Reporting of Disjoint
Paths . . . . . . . . . . . . . . . . . 302--340
Vince Grolmusz Harmonic Analysis, Real Approximation,
and the Communication Complexity of
Boolean Functions . . . . . . . . . . . 341--353
Guoliang Xue and
Ding-Zhu Du An $O(n \log n)$ Average Time Algorithm
for Computing the Shortest Network under
a Given Topology . . . . . . . . . . . . 354--362
Jay Belanger and
Aduri Pavan and
J. Wang Reductions Do Not Preserve Fast
Convergence Rates in Average Time . . . 363--373
Monika Rauch Henzinger and
Valerie King and
Tandy Warnow Constructing a Tree from Homeomorphic
Subtrees, with Applications to
Computational Evolutionary Biology . . . 1--13
Yanjun Zhang and
A. Ortynski Efficiency of Randomized Parallel
Backtrack Search . . . . . . . . . . . . 14--28
Stefano Leonardi and
Alberto Marchetti-Spaccamela On-Line Resource Management with
Application to Routing and Scheduling 29--49
Svante Carlsson and
B. J. Nilsson Computing Vision Points in Polygons . . 50--75
Paul Pritchard A Fast Bit-Parallel Algorithm for
Computing the Subset Partial Order . . . 76--86
Bin Fu and
Richard Beigel A Comparison of Resource-Bounded
Molecular Computation Models . . . . . . 87--95
Haim Kaplan and
Ron Shamir Bounded Degree Interval Sandwich
Problems . . . . . . . . . . . . . . . . 96--104
Koichi Yamazaki and
Hans L. Bodlaender and
Babette de Fluiter and
Dimitrios M. Thilikos Isomorphism for Graphs of Bounded
Distance Width . . . . . . . . . . . . . 105--127
S. Ravi Kumar and
A. Russell and
Ravi Sundaram Approximating Latin Square Extensions 128--138
Frank Thomson Leighton and
Eric J. Schwabe Efficient Algorithms for Dynamic
Allocation of Distributed Memory . . . . 139--171
Frank K. H. A. Dehne Guest Editor's Introduction . . . . . . 173--176
Paolo Ferragina and
Fabrizio Luccio String Search in Coarse-Grained Parallel
Computers . . . . . . . . . . . . . . . 177--194
Afonso Ferreira and
Claire Kenyon and
Andrew Rau-Chaplin and
Stéphane Ubéda $d$-dimensional range search on
multicomputers . . . . . . . . . . . . . 195--208
Armin Bäumker and
Wolfgang Dittrich and
Andrea Pietracaprina The Complexity of Parallel Multisearch
on Coarse-Grained Machines . . . . . . . 209--242
Guy E. Blelloch and
G. L. Miller and
Jonathan C. Hardwick and
Dafna Talmor Design and Implementation of a Practical
Parallel Delaunay Algorithm . . . . . . 243--269
Xiaotie Deng and
Binhai Zhu A Randomized Algorithm for the Vorono\uì
Diagram of Line Segments on
Coarse-Grained Multiprocessors . . . . . 270--286
William F. McColl and
Alexandre Tiskin Memory-Efficient Matrix Multiplication
in the BSP Model . . . . . . . . . . . . 287--297
Yong Won Lim and
Prashanth B. Bhat and
Viktor K. Prasanna Efficient Algorithms for Block-Cyclic
Redistribution of Arrays . . . . . . . . 298--330
Erich Kaltofen and
A. Lobo Distributed Matrix-Free Solution of
Large Sparse Linear Systems over Finite
Fields . . . . . . . . . . . . . . . . . 331--348
Thomas H. Cormen and
James C. Clippinger Performing BMMC Permutations Efficiently
on Distributed-Memory Multiprocessors
with MPI . . . . . . . . . . . . . . . . 349--370
E. L. G. Saukas and
S. W. Song A Note on Parallel Selection on
Coarse-Grained Multicomputers . . . . . 371--380
M. Adler and
Phillip B. Gibbons and
Yossi Matias and
Vijaya Ramachandran Modeling Parallel Bandwidth: Local
versus Global Restrictions . . . . . . . 381--404
Gianfranco Bilardi and
Andrea Pietracaprina and
Geppino Pucci and
Kieran T. Herley and
Paul G. Spirakis BSP versus LogP . . . . . . . . . . . . 405--422
Ming-Yang Kao and
A. S. Kyle and
P. Lakner Guest Editors' Foreword . . . . . . . . 1
Prasad Chalasani and
Somesh Jha and
Isaac Saias Approximate Option Pricing . . . . . . . 2--21
Yossi Azar and
Yair Bartal and
Esteban Feuerstein and
Amos Fiat and
Stefano Leonardi and
Adi Rosén On Capital Investment . . . . . . . . . 22--36
C. G. Lambert and
S. E. Harrington and
C. R. Harvey and
A. Glodjo Efficient On-Line Nonparametric Kernel
Density Estimation . . . . . . . . . . . 37--57
E. J. Kontoghiorghes Parallel Strategies for Computing the
Orthogonal Factorizations Used in the
Estimation of Econometric Models . . . . 58--74
L. N. Coyle and
J. J. Yang Analysis of the SSAP Method for the
Numerical Valuation of High-Dimensional
Multivariate American Securities . . . . 75--98
Sabah al-Binali A Risk-Reward Framework for the
Competitive Analysis of Financial Games 99--115
Ran El-Yaniv and
R. Kaniel and
Nathan Linial Competitive Optimal On-Line Leasing . . 116--140
Dan Gusfield and
Ming-Yang Kao Guest Editors' Foreword . . . . . . . . 141
John H. Reif Parallel Biomolecular Computation:
Models and Simulations . . . . . . . . . 142--175
B. DasGupta and
X. He and
Tao Jiang and
Ming Li and
John Tromp On the Linear-Cost Subtree-Transfer
Distance between Phylogenetic Trees . . 176--195
Paul E. Kearney and
Ryan B. Hayward and
Henk Meijer Evolutionary Trees and Ordinal
Assertions . . . . . . . . . . . . . . . 196--221
Richard Beigel and
Bin Fu Molecular Computing, Bounded
Nondeterminism, and Efficient Recursion 222--238
Mitsunori Ogihara and
Animesh Ray Simulating Boolean Circuits on a DNA
Computer . . . . . . . . . . . . . . . . 239--250
Kevin Atteson The Performance of Neighbor-Joining
Methods of Phylogenetic Reconstruction 251--278
John Atkins and
William E. Hart On the Intractability of Protein Folding
with a Finite Alphabet of Amino Acids 279--294
Laxmi Parida and
Dan Geiger Mass Estimation of DNA Molecules and
Extraction of Ordered Restriction Maps
in Optical Mapping Imagery . . . . . . . 295--310
Mary Cryan and
Leslie Ann Goldberg and
Cynthia A. Phillips Approximation Algorithms for the
Fixed-Topology Phylogenetic Number
Problem . . . . . . . . . . . . . . . . 311--329
T. C. Ip and
Vincemt A. Fischetti and
Jeanette P. Schmidt An Algorithm for Identifying Similar
Amino Acid Clusters among Different
Alpha-Helical Coiled-Coil Proteins Using
Their Secondary Structure . . . . . . . 330--346
Paul W. Finn and
Lydia E. Kavraki Computational Approaches to Drug Design 347--371
Ioannis Z. Emiris and
Bernard Mourrain Computer Algebra Methods for Studying
and Computing Molecular Conformations 372--402
Joan Boyar and
Kim S. Larsen The Seat Reservation Problem . . . . . . 403--417
Martin Zachariasen and
Pawel Winter Concatenation-based greedy heuristics
for the Euclidean Steiner tree problem 418--437
Manfred Kunde and
Rolf Niedermeier and
Klaus Reinhardt and
Peter Rossmanith Optimal Deterministic Sorting and
Routing on Grids and Tori with Diagonals 438--458
Takao Nishizeki and
Roberto Tamassia and
Dorothea Wagner Foreword . . . . . . . . . . . . . . . . 1--2
Xiao Zhou and
Syurei Tamura and
Takao Nishizeki Finding edge-disjoint paths in partial
$k$-trees . . . . . . . . . . . . . . . 3--30
Shiva Chaudhuri and
K. V. Subrahmanyam and
Frank Wagner and
Christos D. Zaroliagis Computing Mimicking Networks . . . . . . 31--49
Hiroshi Nagamochi and
S. Nakamura and
Toshihide Ibaraki A Simplified $\tilde{O}(nm)$ Time
Edge-Splitting Algorithm in Undirected
Graphs . . . . . . . . . . . . . . . . . 50--67
Ulrich Fößmeier and
Michael Kaufmann On Exact Solutions for the Rectilinear
Steiner Tree Problem. Part I:
Theoretical Results . . . . . . . . . . 68--99
Achilleas Papakostas and
Ioannis G. Tollis Efficient Orthogonal Drawings of High
Degree Graphs . . . . . . . . . . . . . 100--125
Karsten Weihe and
Thomas Willhalm Reconstructing the Topology of a CAD
Model --- a Discrete Approach . . . . . 126--147
Rolf H. Möhring and
Matthias Müller-Hannemann Complexity and Modeling Aspects of Mesh
Refinement into Quadrilaterals . . . . . 148--171
Michael Jünger and
G. Rinaldi and
S. Thienel Practical Performance of Efficient
Minimum Cut Algorithms . . . . . . . . . 172--195
Esther M. Arkin and
Martin Held and
Christopher L. Smith Optimization Problems Related to Zigzag
Pocket Machining . . . . . . . . . . . . 197--236
Pascal Berthomé and
Afonso Ferreira and
Bruce M. Maggs and
Stéphane Perennes and
C. Greg Plaxton Sorting-Based Selection Algorithms for
Hypercubic Networks . . . . . . . . . . 237--254
Ee-Chien Chang and
Chee K. Yap A Simultaneous Search Problem . . . . . 255--262
M. G. Andrews and
Mikhail J. Atallah and
Danny Z. Chen and
D. T. Lee Parallel Algorithms for Maximum Matching
in Complements of Interval Graphs and
Related Problems . . . . . . . . . . . . 263--289
Takeaki Uno and
Mutsunori Yagiura Fast Algorithms to Enumerate All Common
Intervals of Two Permutations . . . . . 290--309
Rajeev Motwani and
P. Raghavan Guest Editors' Foreword . . . . . . . . 311--312
S. Akella and
Wes H. Huang and
Kevin M. Lynch and
Matthew T. Mason Parts Feeding on a Conveyor with a One
Joint Robot . . . . . . . . . . . . . . 313--344
Marek Teichmann and
Bud Mishra Probabilistic Algorithms for Efficient
Grasping and Fixturing . . . . . . . . . 345--363
Amy J. Briggs and
Bruce Randall Donald Visibility-Based Planning of Sensor
Control Strategies . . . . . . . . . . . 364--388
Karl-Friedrich Böhringer and
V. Bhatt and
Bruce Randall Donald and
Ken Goldberg Algorithms for Sensorless Manipulation
Using a Vibrating Surface . . . . . . . 389--429
Steven M. LaValle Robot Motion Planning: A Game-Theoretic
Foundation . . . . . . . . . . . . . . . 430--465
A. Sudsang and
J. Ponce and
N. Srinivasa Grasping and In-Hand Manipulation:
Geometry and Algorithms . . . . . . . . 466--493
A. Frank van der Stappen and
Ken Goldberg and
M. H. Overmars Geometric Eccentricity and the
Complexity of Manipulation Plans . . . . 494--514
R. G. Brown and
Bruce Randall Donald Mobile Robot Self-Localization without
Explicit Landmarks . . . . . . . . . . . 515--559
A. Marigo and
Marco Ceccarelli and
S. Piccinocchi and
A. Bicchi Planning Motions of Polyhedral Parts by
Rolling . . . . . . . . . . . . . . . . 560--576
Dan Halperin and
Jean-Claude Latombe and
Randall H. Wilson A General Framework for Assembly
Planning: The Motion Space Approach . . 577--601
Steven Fortune Introduction . . . . . . . . . . . . . . 1--4
Kokichi Sugihara and
Masao Iri and
Hiroshi Inagaki and
T. Imai Topology-Oriented Implementation --- An
Approach to Robust Geometric Algorithms 5--20
Hervé Brönnimann and
Mariette Yvinec Efficient Exact Evaluation of Signs of
Determinants . . . . . . . . . . . . . . 21--56
Victor J. Milenkovic Shortest Path Geometric Rounding . . . . 57--86
Christoph Burnikel and
Rudolf Fleischer and
Kurt Mehlhorn and
Stefan Schirra A Strong and Easily Computable
Separation Bound for Arithmetic
Expressions Involving Radicals . . . . . 87--99
Chandrajit L. Bajaj and
Andrew V. Royappa Parameterization in Finite Precision . . 100--114
Luca Trevisan Erratum: ``Parallel approximation
algorithms by positive linear
programming'' [Algorithmica \bf 21
(1998), no. 1, 72--88; MR1612219
(99a:90130)] . . . . . . . . . . . . . . 115--119
Sanjiv Kapoor and
H. Ramesh An Algorithm for Enumerating All
Spanning Trees of a Directed Graph . . . 120--130
Reuven Bar-Yehuda One for the Price of Two: a Unified
Approach for Approximating Covering
Problems . . . . . . . . . . . . . . . . 131--144
Gonzalo Navarro and
Ricardo A. Baeza-Yates and
Eduardo F. Barbosa and
Nivio Ziviani and
Walter Cunto Binary Searching with Nonuniform Costs
and Its Application to Text Retrieval 145--169
Elmar Schömer and
Jürgen Sellen and
Marek Teichmann and
Chee K. Yap Smallest Enclosing Cylinders . . . . . . 170--186
G. Sajith and
Sanjeev Saxena Optimal Sublogarithmic Time Parallel
Algorithms on Rooted Forests . . . . . . 187--197
Nili Guttmann-Beck and
Refael Hassin Approximation Algorithms for Minimum
$K$-Cut . . . . . . . . . . . . . . . . 198--207
Hans L. Bodlaender Introduction . . . . . . . . . . . . . . 209--211
Shiva Chaudhuri and
Christos D. Zaroliagis Shortest Paths in Digraphs of Small
Treewidth. Part I: Sequential Algorithms 212--226
Xiao Zhou and
K. Fuse and
Takao Nishizeki A Linear Algorithm for Finding [$g$,
$f$]-Colorings of Partial $k$-Trees . . 227--243
Stephen Alstrup and
Peter W. Lauridsen and
Mikkel Thorup Generalized Dominators for Structured
Programs . . . . . . . . . . . . . . . . 244--253
Arvind Gupta and
Damon Kaller and
Thomas C. Shermer Linear-Time Algorithms for Partial
$k$-Tree Complements . . . . . . . . . . 254--274
David Eppstein Diameter and Treewidth in Minor-Closed
Graph Families . . . . . . . . . . . . . 275--291
Torben Hagerup Dynamic Algorithms for Graphs of Bounded
Treewidth . . . . . . . . . . . . . . . 292--315
C. Lucet and
J.-F. Manouvrier and
J. Carlier Evaluating Network Reliability and
2-Edge-Connected Reliability in Linear
Time for Bounded Pathwidth Graphs . . . 316--336
Anders Dessmark and
Andrzej Lingas and
Andrzej Proskurowski Faster algorithms for subgraph
isomorphism of $k$-connected partial
$k$-trees . . . . . . . . . . . . . . . 337--347
Damon Kaller Definability equals recognizability of
partial $3$-trees and $k$-connected
partial $k$-trees . . . . . . . . . . . 348--381
Bengt Aspvall and
Jan Arne Telle and
Andrzej Proskurowski Memory requirements for table
computations in partial $k$-tree
algorithms . . . . . . . . . . . . . . . 382--394
Sheng-Lung Peng and
Chuan Yi Tang and
Ming-Tat Ko and
Chin-Wen Ho and
Tsan-sheng Hsu Graph Searching on Some Subclasses of
Chordal Graphs . . . . . . . . . . . . . 395--426
Gerhard J. Woeginger Introduction . . . . . . . . . . . . . . 1
Johannes Blömer Denesting by Bounded Degree Radicals . . 2--15
Ulrik Brandes and
Dorothea Wagner A Linear Time Algorithm for the Arc
Disjoint Menger Problem in Planar
Directed Graphs . . . . . . . . . . . . 16--36
Krzysztof Diks and
Andrzej Pelc Optimal Adaptive Broadcasting with a
Bounded Fraction of Faulty Nodes . . . . 37--50
Hristo N. Djidjev Partitioning Planar Graphs with Vertex
Costs: Algorithms and Applications . . . 51--75
Daniele Frigioni and
Giuseppe F. Italiano Dynamically Switching Vertices in Planar
Graphs . . . . . . . . . . . . . . . . . 76--103
Vladimir Grebinski and
Gregory Kucherov Optimal Reconstruction of Graphs under
the Additive Model . . . . . . . . . . . 104--124
Bala Kalyanasundaram and
Kirk Pruhs Fault-Tolerant Real-Time Scheduling . . 125--144
Luca Trevisan Approximating Satisfiable Satisfiability
Problems . . . . . . . . . . . . . . . . 145--172
Steven S. Seiden Online Randomized Multiprocessor
Scheduling . . . . . . . . . . . . . . . 173--216
Danny Z. Chen and
Wei Chen and
Koichi Wada and
Kimio Kawaguchi Parallel Algorithms for Partitioning
Sorted Sets and Related Problems . . . . 217--241
Eric Ruppert Finding the $k$ shortest paths in
parallel . . . . . . . . . . . . . . . . 242--254
Teofilo F. Gonzalez Simple Algorithms for the On-Line
Multidimensional Dictionary and Related
Problems . . . . . . . . . . . . . . . . 255--267
Bala Kalyanasundaram and
Kirk R. Pruhs and
Eric Torng Errata: ``A new algorithm for scheduling
periodic, real-time tasks''
[Algorithmica \bf 4 (1989), no. 4,
209--219; MR0988726 (90k:68017)] by J.
Y.-T. Leung . . . . . . . . . . . . . . 269--270
John H. Reif and
S. R. Tate Fast Spatial Decomposition and Closest
Pair Computation for Limited Precision
Input . . . . . . . . . . . . . . . . . 271--287
Desh Ranjan and
Enrico Pontelli and
Gopal Gupta and
Luc Longpré The Temporal Precedence Problem . . . . 288--306
J. García-López and
P. A. Ramos A Unified Approach to Conic Visibility 307--322
Lenwood S. Heath and
J. P. C. Vergara Sorting by Short Block-Moves . . . . . . 323--352
Mark de Berg Linear Size Binary Space Partitions for
Uncluttered Scenes . . . . . . . . . . . 353--366
Hristo N. Djidjev and
Grammati E. Pantziou and
Christos D. Zaroliagis Improved Algorithms for Dynamic Shortest
Paths . . . . . . . . . . . . . . . . . 367--389
Hsiao-Feng Steven Chen and
D. T. Lee A Faster One-Dimensional Topological
Compaction Algorithm with Jog Insertion 390--421
Nili Guttmann-Beck and
Refael Hassin and
Samir Khuller and
Balaji Raghavachari Approximation Algorithms with Bounded
Performance Guarantees for the Clustered
Traveling Salesman Problem . . . . . . . 422--437
Bruce M. Maggs and
Berthold Vöcking Improved Routing and Sorting on
Multibutterflies . . . . . . . . . . . . 438--464
Helmut Prodinger and
Wojciech Szpankowski Average-Case Analysis of Algorithms ---
Preface . . . . . . . . . . . . . . . . 1--2
U. Rösler and
L. Rüschendorf The Contraction Method for Recursive
Algorithms . . . . . . . . . . . . . . . 3--33
George E. Andrews and
Arnold Knopfmacher An algorithmic approach to discovering
and proving $q$-series identities . . . 34--43
H.-H. Chern and
Hsien-Kuei Hwang Transitional behaviors of the average
cost of Quicksort with
median-of-$(2t+1)$ . . . . . . . . . . . 44--69
Edward G. Coffman, Jr. and
Alexander L. Stolyar Bandwidth Packing . . . . . . . . . . . 70--88
Michael Drmota An Analytic Approach to the Height of
Binary Search Trees . . . . . . . . . . 89--119
Michael Drmota and
Dani\`ele Gardy and
B. Gittenberger A Unified Presentation of Some Urn
Models . . . . . . . . . . . . . . . . . 120--147
J. C. Hansen and
E. Schmutz Near-Optimal Bounded-Degree Spanning
Trees . . . . . . . . . . . . . . . . . 148--180
Conrado Martínez and
Alois Panholzer and
Helmut Prodinger Partial Match Queries in Relaxed
Multidimensional Search Trees . . . . . 181--204
Daniel Panario and
B. Richmond Smallest Components in Decomposable
Structures: Exp-Log Class . . . . . . . 205--226
Patricio V. Poblete Analysis of an Adaptive Algorithm to
Find the Two Nearest Neighbors . . . . . 227--237
U. Rösler On the Analysis of Stochastic Divide and
Conquer Algorithms . . . . . . . . . . . 238--261
Brigitte Vallée Dynamical Sources in Information Theory:
Fundamental Intervals and Word Prefixes 262--306
Julien Clément and
Philippe Flajolet and
Brigitte Vallée Dynamical Sources in Information Theory:
A General Analysis of Trie Structures 307--369
S. Mahajan and
E. A. Ramos and
K. V. Subrahmanyam Solving Some Discrepancy Problems in NC 371--395
L. Narayanan and
S. M. Shende Static Frequency Assignment in Cellular
Networks . . . . . . . . . . . . . . . . 396--409
U. Feige and
G. Kortsarz and
D. Peleg The dense $k$-subgraph problem . . . . . 410--421
A. Avidor and
Y. Azar and
J. Sgall Ancient and New Algorithms for Load
Balancing in the $l_p$ Norm . . . . . . 422--441
H. Shachnai and
T. Tamir On Two Class-Constrained Versions of the
Multiple Knapsack Problem . . . . . . . 442--467
M. J. Atallah and
F. Chyzak and
P. Dumas A Randomized Algorithm for Approximate
String Matching . . . . . . . . . . . . 468--486
J. H. Reif Efficient Parallel Computation of the
Characteristic Polynomial of a Sparse,
Separable Matrix . . . . . . . . . . . . 487--510
T. F. Gonzalez Simple Algorithms for Multimessage
Multicasting with Forwarding . . . . . . 511--533
H. L. Bodlaender and
B. van Antwerpen--de Fluiter Parallel Algorithms for Series Parallel
Graphs and Graphs with Treewidth Two . . 534--559
G. Ausiello and
E. Feuerstein and
S. Leonardi and
L. Stougie and
M. Talamo Algorithms for the On-Line Travelling
Salesman . . . . . . . . . . . . . . . . 560--581
S. N. Kabadi and
Y. P. Aneja Equivalence of $\epsilon$-Approximate
Separation and Optimization in Fixed
Dimensions . . . . . . . . . . . . . . . 582--594
R. Bar-Yehuda and
D. Rawitz Efficient Algorithms for Integer
Programs with Two Variables per
Constraint . . . . . . . . . . . . . . . 595--609
R. Battiti and
M. Protasi Reactive Local Search for the Maximum
Clique Problem . . . . . . . . . . . . . 610--637
J. F. Weng and
J. MacGregor Smith Steiner Minimal Trees with One Polygonal
Obstacle . . . . . . . . . . . . . . . . 638--648
D. Fernández-Baca On Nonlinear Parametric Search . . . . . 1--11
T. W. Lam and
F. L. Yue Optimal Edge Ranking of Trees in Linear
Time . . . . . . . . . . . . . . . . . . 12--33
A. M. Ben-Amram and
Z. Galil A Generalization of a Lower Bound
Technique due to Fredman and Saks . . . 34--66
J.-D. Boissonnat and
J. Czyzowicz and
O. Devillers and
M. Yvinec Circular Separability of Polygons . . . 67--82
D. J. Rosenkrantz and
L. Yu and
S. S. Ravi Efficient Construction of Minimum
Makespan Schedules for Tasks with a
Fixed Number of Distinct Execution Times 83--100
R. El-Yaniv and
A. Fiat and
R. M. Karp and
G. Turpin Optimal Search and One-Way Trading
Online Algorithms . . . . . . . . . . . 101--139
M. van Kreveld Guest Editor's Foreword . . . . . . . . 141--143
C. Gold and
J. Snoeyink A One-Step Crust and Skeleton Extraction
Algorithm . . . . . . . . . . . . . . . 144--163
A. Amir and
A. Efrat and
P. Indyk and
H. Samet Efficient Regular Data Structures and
Algorithms for Dilation, Location, and
Proximity Problems . . . . . . . . . . . 164--187
D. Papadias and
N. Mamoulis and
Y. Theodoridis Constraint-Based Processing of Multiway
Spatial Joins . . . . . . . . . . . . . 188--215
V. Estivill-Castro and
M. E. Houle Robust Distance-Based Clustering with
Applications to Spatial Data Mining . . 216--242
J. J. Little and
P. Shi Structural Lines, TINs, and DEMs . . . . 243--263
W. Evans and
D. Kirkpatrick and
G. Townsend Right-Triangulated Irregular Networks 264--286
M. Lonergan and
C. B. Jones An Iterative Displacement Method for
Conflict Resolution in Map
Generalization . . . . . . . . . . . . . 287--301
W. A. Mackaness and
R. S. Purves Automated Displacement for Large Numbers
of Discrete Map Objects . . . . . . . . 302--311
N. Regnauld Contextual Building Typification in
Automated Map Generalization . . . . . . 312--333
F. Wagner and
A. Wolff and
V. Kapoor and
T. Strijk Three Rules Suffice for Good Label
Placement . . . . . . . . . . . . . . . 334--349
K. Jansen and
J. Rolim Guest Editors' Introduction . . . . . . 351--352
J. Cheriyan and
T. Jordán and
Z. Nutov On Rooted Node-Connectivity Problems . . 353--375
P. Tetali and
S. Vempala Random Sampling of Euler Tours . . . . . 376--385
M. Karpinski Polynomial Time Approximation Schemes
for Some Dense Instances of NP-Hard
Optimization Problems . . . . . . . . . 386--397
M. I. Sviridenko Best possible approximation algorithm
for MAX SAT with cardinality constraint 398--405
V. Kumar An Approximation Algorithm for Circular
Arc Colouring . . . . . . . . . . . . . 406--417
M. Saks and
S. Zhou Sample Spaces with Small Bias on
Neighborhoods and Error-Correcting
Communication Protocols . . . . . . . . 418--431
G. Kortsarz On the Hardness of Approximating
Spanners . . . . . . . . . . . . . . . . 432--450
C. Baur and
S. P. Fekete Approximation of Geometric Dispersion
Problems . . . . . . . . . . . . . . . . 451--470
G. F. Italiano Guest Editor's Introduction . . . . . . 471--472
G. Navarro and
R. Baeza-Yates Improving an Algorithm for Approximate
Pattern Matching . . . . . . . . . . . . 473--502
A. L. Buchsbaum and
R. Giancarlo and
J. R. Westbrook An Approximate Determinization Algorithm
for Weighted Finite-State Automata . . . 503--526
M. Lanthier and
A. Maheshwari and
J.-R. Sack Approximating Shortest Paths on Weighted
Polyhedral Surfaces . . . . . . . . . . 527--562
M. Held FIST: fast industrial-strength
triangulation of polygons . . . . . . . 563--596
T. Christof and
G. Reinelt Algorithmic Aspects of Using Small
Instance Relaxations in Parallel
Branch-and-Cut . . . . . . . . . . . . . 597--629
B. de Jager and
J. Banens VISOR: vast independence system
optimization routine . . . . . . . . . . 630--644
M. Lee and
W. Liu and
V. K. Prasanna Parallel Implementation of a Class of
Adaptive Signal Processing Applications 645--684
B. Codenotti and
M. Leoncini and
F. P. Preparata The Role of Arithmetic in Fast Parallel
Matrix Inversion . . . . . . . . . . . . 685--707
V. Y. Pan and
Y. Yu Certification of Numerical Computation
of the Sign of the Determinant of a
Matrix . . . . . . . . . . . . . . . . . 708--724
A. Efrat and
A. Itai and
M. J. Katz Geometry Helps in Bottleneck Matching
and Related Problems . . . . . . . . . . 1--28
B. Awerbuch and
Y. Azar and
A. Fiat and
S. Leonardi and
A. Rosén On-Line Competitive Algorithms for Call
Admission in Optical Networks . . . . . 29--43
J. C. Cogolludo and
S. Rajasekaran Permutation Routing on Reconfigurable
Meshes . . . . . . . . . . . . . . . . . 44--57
R. Ravi and
M. V. Marathe and
S. S. Ravi and
D. J. Rosenkrantz and
H. B. Hunt, III Approximation Algorithms for
Degree-Constrained Minimum-Cost
Network-Design Problems . . . . . . . . 58--78
S. Eidenbenz and
C. Stamm and
P. Widmayer Inapproximability Results for Guarding
Polygons and Terrains . . . . . . . . . 79--113
J. Csirik and
D. S. Johnson Bounded Space On-Line Bin Packing: Best
Is Better than First . . . . . . . . . . 115--138
M. C. Golumbic and
T. Hirst and
M. Lewenstein Uniquely Restricted Matchings . . . . . 139--154
L. Narayanan and
J. Opatrny and
D. Sotteau All-to-All Optical Routing in Chordal
Rings of Degree 4 . . . . . . . . . . . 155--178
N. Gupta and
S. Sen An Efficient Output-Size Sensitive
Parallel Algorithm for Hidden-Surface
Removal for Terrains . . . . . . . . . . 179--207
M. Yamashita and
H. Umemoto and
I. Suzuki and
T. Kameda Searching for Mobile Intruders in a
Polygonal Region by a Group of Mobile
Searchers . . . . . . . . . . . . . . . 208--236
R. Kemp and
H. Prodinger Preface . . . . . . . . . . . . . . . . 237--239
V. Choi and
M. J. Golin Lopsided trees. I. Analyses . . . . . . 240--290
L. Devroye On the Probabilistic Worst-Case Time of
``Find'' . . . . . . . . . . . . . . . . 291--303
M. Drmota The Asymptotic Number of Leftist Trees 304--317
P. Jacquet and
W. Szpankowski and
J. Tang Average profile of the Lempel--Ziv
parsing scheme for a Markovian source 318--360
P. Flajolet and
G. Louchard Analytic Variations on the Airy
Distribution . . . . . . . . . . . . . . 361--377
M. Hofri and
H. Shachnai Efficient Reorganization of Binary
Search Trees . . . . . . . . . . . . . . 378--402
T. Tsukiji and
H. Mahmoud A Limit Law for Outputs in Random
Recursive Circuits . . . . . . . . . . . 403--412
D. Panario and
B. Richmond Exact Largest and Smallest Size of
Components . . . . . . . . . . . . . . . 413--432
H. Prodinger A $q$-analogue of the path length of
binary search trees . . . . . . . . . . 433--441
R. T. Smythe and
J. Wellner Stochastic Analysis of Shell Sort . . . 442--457
P. A. Beling Exact Algorithms for Linear Programming
over Algebraic Extensions . . . . . . . 459--478
G. Xue and
G.-H. Lin and
D.-Z. Du Grade of Service Steiner Minimum Trees
in the Euclidean Plane . . . . . . . . . 479--500
K. S. Larsen and
E. Soisalon-Soininen and
P. Widmayer Relaxed Balance Using Standard Rotations 501--512
R. L. Milidiú and
E. S. Laber Bounding the Inefficiency of
Length-Restricted Prefix Codes . . . . . 513--529
B. Das and
M. C. Loui Reconstructing a Minimum Spanning Tree
after Deletion of Any Node . . . . . . . 530--547
A. Crauser and
P. Ferragina A Theoretical and Experimental Study on
the Construction of Suffix Arrays in
External Memory . . . . . . . . . . . . 1--35
E. Feuerstein and
A. Strejilevich de Loma On-Line Multi-Threaded Paging . . . . . 36--60
J. G. Del Greco and
C. N. Sekharan and
R. Sridhar Fast parallel reordering and isomorphism
testing of $k$-trees . . . . . . . . . . 61--72
D. Gusfield and
C. Martel The Structure and Complexity of Sports
Elimination Numbers . . . . . . . . . . 73--86
D. Eppstein and
M. W. Bern and
B. Hutchings Algorithms for Coloring Quadtrees . . . 87--94
Y. Li and
W. F. Smyth Computing the Cover Array in Linear Time 95--106
T. Kimbrel Interleaved Prefetching . . . . . . . . 107--122
S. Albers and
K. Kursawe and
S. Schuierer Exploring Unknown Environments with
Obstacles . . . . . . . . . . . . . . . 123--143
C. Levcopoulos and
G. Narasimhan and
M. Smid Improved Algorithms for Constructing
Fault-Tolerant Spanners . . . . . . . . 144--156
E. Bax and
J. Franklin A Permanent Algorithm with
$\exp[\Omega(n^{1/3}/2 \ln n)]$ Expected
Speedup for $0$--$1$ Matrices . . . . . 157--162
C. A. Phillips and
C. Stein and
E. Torng and
J. Wein Optimal Time-Critical Scheduling via
Resource Augmentation . . . . . . . . . 163--200
R. Bachrach and
R. El-Yaniv and
M. Reinstädtler On the Competitive Theory and Practice
of Online List Accessing Algorithms . . 201--246
A. K. Amoura and
E. Bampis and
C. Kenyon and
Y. Manoussakis Scheduling Independent Multiprocessor
Tasks . . . . . . . . . . . . . . . . . 247--261
Y. Kamidoi and
S. Wakabayashi and
N. Yoshida A divide-and-conquer approach to the
minimum $k$-way cut problem . . . . . . 262--276
M. Andrews and
M. A. Bender and
L. Zhang New Algorithms for Disk Scheduling . . . 277--301
O. Goldreich and
D. Ron Property Testing in Bounded Degree
Graphs . . . . . . . . . . . . . . . . . 302--343
J. F. Sibeyn One-by-One Cleaning for Practical
Parallel List Ranking . . . . . . . . . 345--363
A. M. Ben-Amram and
Z. Galil Lower Bounds for Dynamic Data Structures
on Algebraic RAMs . . . . . . . . . . . 364--395
D. A. Fotakis and
P. G. Spirakis Minimum Congestion Redundant Assignments
to Tolerate Random Faults . . . . . . . 396--422
S. Landau and
N. Immerman Embedding Linkages on an Integer Lattice 423--436
J. Abello and
A. L. Buchsbaum and
J. R. Westbrook A Functional Approach to External Graph
Algorithms . . . . . . . . . . . . . . . 437--458
E. Cohen and
H. Kaplan Caching Documents with Variable Sizes
and Fetching Costs: An LP-Based Approach 459--466
T. Erlebach and
T. Hagerup Routing Flow Through a Strongly
Connected Graph . . . . . . . . . . . . 467--473
P. Bertolazzi and
G. Di Battista and
W. Didimo Quasi-Upward Planarity . . . . . . . . . 474--506
K. Jansen and
L. Porkolab Linear-Time Approximation Schemes for
Scheduling Malleable Parallel Tasks . . 507--520
P. K. Agarwal and
B. K. Bhattacharya and
S. Sen Improved Algorithms for Uniform
Partitions of Points . . . . . . . . . . 521--539
B. Awerbuch and
T. Singh An Online Algorithm for the Dynamic
Maximal Dense Tree Problem . . . . . . . 540--553
L. Wang and
D.-Z. Du Approximations for a Bottleneck Steiner
Tree Problem . . . . . . . . . . . . . . 554--561
Tzuoo-Hawn Yeh and
Cheng-Ming Kuo and
Chin-Laung Lei and
Hsu-Chun Yen Distributed and On-Line Routing on Tori 562--593
H. J. Broersma and
T. Kloks and
D. Kratsch and
H. Müller A Generalization of AT-Free Graphs and a
Generic Algorithm for Solving
Triangulation Problems . . . . . . . . . 594--610
N. Alon and
A. Zaks Algorithmic Aspects of Acyclic Edge
Colorings . . . . . . . . . . . . . . . 611--614
U. Schöning A probabilistic algorithm for $k$-SAT
based on limited local search and
restart . . . . . . . . . . . . . . . . 615--623
S. Irani Randomized Weighted Caching with Two
Page Weights . . . . . . . . . . . . . . 624--640
A. Ambainis and
S. A. Bloch and
D. L. Schweizer Delayed binary search, or Playing twenty
questions with a procrastinator . . . . 641--651
H. Shachnai and
T. Tamir Multiprocessor Scheduling with Machine
Allotment and Parallelism Constraints 651--678
L. Narayanan and
S. Shende Corrigendum: ``Static frequency
assignment in cellular networks''
[Algorithmica \bf 29 (2001), no. 3,
396--409; MR1799267 (2001i:68016)] . . . 679--679
R. Battiti and
A. Bertossi Foreword . . . . . . . . . . . . . . . . 1--2
L. A. Sanchis Experimental Analysis of Heuristic
Algorithms for the Dominating Set
Problem . . . . . . . . . . . . . . . . 3--18
S. Nilsson and
M. Tikkanen An Experimental Study of Compression
Methods for Dynamic Tries . . . . . . . 19--33
I. D. Baev and
W. M. Meleis and
A. Eichenberger An Experimental Study of Algorithms for
Weighted Completion Time Scheduling . . 34--51
V. Kapoor and
D. Kühl and
A. Wolff A Tutorial for Designing Flexible
Geometric Algorithms . . . . . . . . . . 52--70
A. Bertoni and
P. Campadelli and
G. Grossi A Neural Algorithm for the Maximum
Clique Problem: Analysis, Experiments,
and Circuit Implementation . . . . . . . 71--88
R. N. Wright and
S. Spalding Experimental Performance of Shared RSA
Modulus Generation . . . . . . . . . . . 89--103
L. Arge and
K. H. Hinrichs and
J. Vahrenhold and
J. S. Vitter Efficient Bulk Operations on Dynamic
R-Trees . . . . . . . . . . . . . . . . 104--128
B. Ayeb Fault Identification in System-Level
Diagnosis: a Logic-Based Framework and
an $O(n^2 \sqrt\tau/\sqrt{\log n})$
Algorithm . . . . . . . . . . . . . . . 129--149
G. Barequet and
D. Z. Chen and
O. Daescu and
M. T. Goodrich and
J. Snoeyink Efficiently Approximating Polygonal
Paths in Three and Higher Dimensions . . 150--167
M. R. Korupolu and
V. Ramachandran Quasi-Fully Dynamic Algorithms for
Two-Connectivity and Cycle Equivalence 168--182
F. Dehne and
A. Ferreira and
E. Cáceres and
S. W. Song and
A. Roncato Efficient Parallel Graph Algorithms for
Coarse-Grained Multicomputers and BSP 183--200
P. K. Agarwal and
C. M. Procopiuc Exact and Approximation Algorithms for
Clustering . . . . . . . . . . . . . . . 201--226
P. K. Agarwal and
S. Har-Peled and
M. Karia Computing Approximate Shortest Paths on
Convex Polytopes . . . . . . . . . . . . 227--242
V. Chepoi and
Y. Vaxes Augmenting Trees to Meet Biconnectivity
and Diameter Constraints . . . . . . . . 243--262
S. Bespamyatnikh and
M. Segal Fast Algorithms for Approximating
Distances . . . . . . . . . . . . . . . 263--269
Y. Bartal and
M. Farach-Colton and
S. Yooseph and
L. Zhang Fast, Fair and Frugal Bandwidth
Allocation in ATM Networks . . . . . . . 272--286
H. Kawazoe and
T. Shibuya and
T. Tokuyama Optimal Online Algorithms for an
Electronic Commerce Money Distribution
System . . . . . . . . . . . . . . . . . 287--299
E. Cohen and
H. Kaplan Exploiting Regularities in Web Traffic
Patterns for Cache Replacement . . . . . 300--334
A. Goel and
K. Munagala Extending Greedy Multicast Routing to
Delay Sensitive Applications . . . . . . 335--352
B. Kalyanasundaram and
J. Noga and
K. R. Pruhs and
G. J. Woeginger Caching for Web Searching . . . . . . . 353--370
N. E. Young On-Line File Caching . . . . . . . . . . 371--383
S. Irani Page Replacement with Multi-Size Pages
and Applications to Web Caching . . . . 384--409
Michael T. Goodrich Guest Editor's Foreword . . . . . . . . ??
P. Bose and
F. Hurtado-Diaz and
E. Omaña-Pulido and
J. Snoeyink and
G. T. Toussaint Some Aperture-Angle Optimization
Problems . . . . . . . . . . . . . . . . 411--435
S. Rajasekaran and
S. Ramaswami Optimal Parallel Randomized Algorithms
for the Vorono\uì Diagram of Line
Segments in the Plane . . . . . . . . . 436--460
J. Alber and
H. L. Bodlaender and
H. Fernau and
T. Kloks and
R. Niedermeier Fixed Parameter Algorithms for
DOMINATING SET and Related Problems on
Planar Graphs . . . . . . . . . . . . . 461--493
G. S. Brodal and
C. Makris and
S. Sioutas and
A. Tsakalidis and
K. Tsichlas Optimal Solutions for the Temporal
Precedence Problem . . . . . . . . . . . 494--510
E. Cohen and
H. Kaplan and
U. Zwick Competitive Analysis of the LRFU Paging
Algorithm . . . . . . . . . . . . . . . 511--516
T. M. Chan A Near-Linear Area Bound for Drawing
Binary Trees . . . . . . . . . . . . . . 1--13
P. C. Fishburn and
J. C. Lagarias Pinwheel Scheduling: Achievable
Densities . . . . . . . . . . . . . . . 14--38
B. Chazelle and
O. Devillers and
F. Hurtado and
M. Mora and
V. Sacristán and
M. Teillaud Splitting a Delaunay Triangulation in
Linear Time . . . . . . . . . . . . . . 39--46
T. Jansen and
I. Wegener The Analysis of Evolutionary
Algorithms--A Proof That Crossover
Really Can Help . . . . . . . . . . . . 47--66
J. Feigenbaum and
S. Kannan and
M. Strauss and
M. Viswanathan Testing and Spot-Checking of Data
Streams . . . . . . . . . . . . . . . . 67--80
Mark de Berg and
Matthew J. Katz and
A. Frank van der Stappen and
Jules Vleugels Realistic Input Models for Geometric
Algorithms . . . . . . . . . . . . . . . 81--97
R. Ravi and
D. P. Williamson Erratum: ``An approximation algorithm
for minimum-cost vertex-connectivity
problems'' [Algorithmica \bf 18 (1997),
no. 1, 21--43; MR1432027 (98a:90126)] 98--107
J.-D. Boissonnat and
S. K. Ghosh and
T. Kavitha and
S. Lazard An Algorithm for Computing a Convex and
Simple Path of Bounded Curvature in a
Simple Polygon . . . . . . . . . . . . . 109--156
Nadia Pisanti and
Marie-France Sagot Further Thoughts on the Syntenic
Distance between Genomes . . . . . . . . 157--180
Yossi Azar and
Joan Boyar and
Lene M. Favrholdt and
Kim S. Larsen and
Morten N. Nielsen and
Leah Epstein Fair versus Unrestricted Bin Packing . . 181--196
Matthew Andrews and
Lisa Zhang Approximation Algorithms for Access
Network Design . . . . . . . . . . . . . 197--215
Olivier Beaumont and
Vincent Boudet and
Fabrice Rastello and
Yves Robert Partitioning a Square into Rectangles:
NP-Completeness and Approximation
Algorithms . . . . . . . . . . . . . . . 217--239
Kazuhisa Makino and
Masafumi Yamashita and
Tiko Kameda Max- and Min-Neighborhood Monopolies . . 240--260
Chunhong Chen and
Elaheh Bozorgzadeh and
Ankur Srivastava and
Majid Sarrafzadeh Budget Management with Applications . . 261--275
Adnan Agbaria and
Yosi Ben-Asher and
Ilan Newman Communication--Processor Tradeoffs in a
Limited Resources PRAM . . . . . . . . . 276--297
Surender Baswana and
Sandeep Sen Planar Graph Blocking for External
Searching . . . . . . . . . . . . . . . 298--308
Michele Mosca and
Alain Tapp Introduction . . . . . . . . . . . . . . 309--313
Gerald Gilbert and
Michael Hamrick Secrecy, Computational Loads and Rates
in Practical Quantum Cryptography . . . 314--339
Hitoshi Inamori Security of Practical Time-Reversed EPR
Quantum Key Distribution . . . . . . . . 340--365
Hitoshi Inamori Security of Practical BB84 Quantum Key
Distribution . . . . . . . . . . . . . . 366--371
Eli Biham and
Michel Boyer and
Gilles Brassard and
Jeroen van de Graaf and
Tal Mor Security of Quantum Key Distribution
against All Collective Attacks . . . . . 372--388
Nicolas Gisin and
Renato Renner and
Stefan Wolf Linking Classical and Quantum Key
Agreement: Is There a Classical Analog
to Bound Entanglement? . . . . . . . . . 389--412
Wim van Dam Quantum Algorithms for Weighing Matrices
and Quadratic Residues . . . . . . . . . 413--428
Peter Hòyer and
Jan Neerbek and
Yaoyun Shi Quantum Complexities of Ordered
Searching, Sorting, and Element
Distinctness . . . . . . . . . . . . . . 429--448
J. Niel de Beaudrap and
Richard Cleve and
John Watrous Sharp Quantum versus Classical Query
Complexity Separations . . . . . . . . . 449--461
Jaikumar Radhakrishnan and
Pranab Sen and
S. Venkatesh The Quantum Complexity of Set Membership 462--479
Thomas P. Hayes and
Samuel Kutin and
Dieter van Melkebeek The Quantum Black-Box Complexity of
Majority . . . . . . . . . . . . . . . . 480--501
Todd A. Brun Remotely Prepared Entanglement: a
Quantum Web Page . . . . . . . . . . . . 502--511
Somshubhro Bandyopadhyay and
P. Oscar Boykin and
Vwani Roychowdhury and
Farrokh Vatan A New Proof for the Existence of
Mutually Unbiased Bases . . . . . . . . 512--528
Paul Benioff The Representation of Numbers in Quantum
Mechanics . . . . . . . . . . . . . . . 529--559
Julien Basch and
Leonidas J. Guibas and
G. D. Ramkumar Reporting Red--Blue Intersections
between Two Sets of Connected Line
Segments . . . . . . . . . . . . . . . . 1--20
Peter Sanders and
Sebastian Egner and
Jan Korst Fast Concurrent Access to Parallel Disks 21--55
Enrico Nardelli and
Guido Proietti and
Peter Widmayer Swapping a Failing Edge of a Single
Source Shortest Paths Tree Is Good and
Fast . . . . . . . . . . . . . . . . . . 56--74
Kurt Mehlhorn and
Peter Sanders Scanning Multiple Sequences via Cache
Memory . . . . . . . . . . . . . . . . . 75--93
Andrea E. F. Clementi and
Paolo Penna and
Afonso Ferreira and
Stéphane Perennes and
Riccardo Silvestri The Minimum Range Assignment Problem on
Linear Radio Networks . . . . . . . . . 95--110
Abraham Punnen and
Francois Margot and
Santosh Kabadi TSP Heuristics: Domination Analysis and
Complexity . . . . . . . . . . . . . . . 111--127
David Pisinger Dynamic Programming on the Word RAM . . 128--145
Claire Kenyon and
Nicolas Schabanel The Data Broadcast Problem with
Non-Uniform Transmission Times . . . . . 146--175
Lene Monrad Favrholdt and
Morten Nyhave Nielsen On-Line Edge-Coloring with a Fixed
Number of Colors . . . . . . . . . . . . 176--191
Mikhail J. Atallah and
Danny Z. Chen and
Ovidiu Daescu Efficient parallel algorithms for planar
$st$-graphs . . . . . . . . . . . . . . 194--215
Kazuyoshi Hidaka and
Hiroyuki Okano An Approximation Algorithm for a
Large-Scale Facility Location Problem 216--224
Yoshiyuki Kusakari and
Takao Nishizeki Finding a Region with the Minimum Total
$L_1$ Distance from Prescribed Terminals 225--256
Chung Keung Poon and
Vijaya Ramachandran A Randomized Linear-Work EREW PRAM
Algorithm to Find a Minimum Spanning
Forest . . . . . . . . . . . . . . . . . 257--268
Hisao Tamaki and
Takeshi Tokuyama A Characterization of Planar Graphs by
Pseudo-Line Arrangements . . . . . . . . 269--285
Hon Wai Leong and
Hiroshi Imai Guest Editors' Foreword . . . . . . . . ??
Subhash Suri and
Tuomas Sandholm and
Priyank Warkhede Compressing Two-Dimensional Routing
Tables . . . . . . . . . . . . . . . . . 287--300
Lars Engebretsen An Explicit Lower Bound for TSP with
Distances One and Two . . . . . . . . . 301--319
Philip N. Klein and
Robert H. B. Netzer and
Hsueh-I Lu Detecting Race Conditions in Parallel
Programs that Use Semaphores . . . . . . 321--345
Veli Mäkinen and
Gonzalo Navarro and
Esko Ukkonen Approximate Matching of Run-Length
Compressed Strings . . . . . . . . . . . 347--369
Pascal Ferraro and
Christophe Godin An Edit Distance between Quotiented
Trees . . . . . . . . . . . . . . . . . 1--39
Louay Bazzi and
Sanjoy Mitter The Solution of Linear Probabilistic
Recurrence Relations . . . . . . . . . . 41--57
Matthew J. Katz and
Frank Nielsen and
Michael Segal Maintenance of a Piercing Set for
Intervals with Applications . . . . . . 59--73
Holger Bast and
Kurt Mehlhorn and
Guido Schäfer and
Hisao Tamaki A Heuristic for Dijkstra's Algorithm
with Many Targets and Its Use in
Weighted Matching Algorithms . . . . . . 75--88
Xiaoming Sun A $3$-Party Simultaneous Protocol for
SUM-INDEX . . . . . . . . . . . . . . . 89--111
Ying Xu An $O(n^{1.5})$ Deterministic Gossiping
Algorithm for Radio Networks . . . . . . 93--96
Frank Dehne and
Wolfgang Dittrich and
David Hutchinson Efficient External Memory Algorithms by
Simulating Coarse-Grained Parallel
Algorithms . . . . . . . . . . . . . . . 97--122
Micah Adler and
Sanjeev Khanna and
Rajmohan Rajaraman and
Adi Rosén Time-Constrained Scheduling of Weighted
Packets on Trees and Meshes . . . . . . 123--152
Seok-Hee Hong and
Peter Eades Drawing Trees Symmetrically in Three
Dimensions . . . . . . . . . . . . . . . 153--178
Gruia C\ualinescu and
Cristina G. Fernandes and
Howard Karloff and
Alexander Zelikovsky A New Approximation Algorithm for
Finding Heavy Planar Subgraphs . . . . . 179--205
Susanne Albers Foreword . . . . . . . . . . . . . . . . 207--208
Anna R. Karlin and
Claire Kenyon and
Dana Randall Dynamic TCP Acknowledgment and Other
Stories about $e/(e - 1)$ . . . . . . . 209--224
Amotz Bar-Noy and
Ari Freund and
Shimon Landa and
Joseph (Seffi) Naor Competitive On-Line Switching Policies 225--247
Avrim Blum and
Shuchi Chawla and
Adam Kalai Static Optimality and Dynamic
Search-Optimality in Lists and Trees . . 249--260
Steven S. Seiden and
Rob van Stee New Bounds for Multidimensional Packing 261--293
Amitai Armon and
Yossi Azar and
Leah Epstein and
Oded Regev Temporary Tasks Assignment Resolved . . 295--314
Jeff Edmonds and
Kirk Pruhs Multicast Pull Scheduling: When Fairness
Is Fine . . . . . . . . . . . . . . . . 315--330
Satoru Iwata Computing the Maximum Degree of Minors
in Matrix Pencils via Combinatorial
Relaxation . . . . . . . . . . . . . . . 331--341
Wun-Tat Chan and
Francis Y. L. Chin and
Hing-Fung Ting Escaping a Grid by Edge-Disjoint Paths 343--359
Anna Galluccio and
Guido Proietti Polynomial Time Algorithms for
$2$-Edge-Connectivity Augmentation
Problems . . . . . . . . . . . . . . . . 361--374
Hans L. Bodlaender and
Udi Rotics Computing the Treewidth and the Minimum
Fill-In with the Modular Decomposition 375--408
Lars Arge The Buffer Tree: A Technique for
Designing Batched External Data
Structures . . . . . . . . . . . . . . . 1--24
Jens Gramm and
Rolf Niedermeier and
Peter Rossmanith Fixed-Parameter Algorithms for CLOSEST
STRING and Related Problems . . . . . . 25--42
Moritz G. Maaß Linear Bidirectional On-Line
Construction of Affix Trees . . . . . . 43--74
Guy Kortsarz and
Zeev Nutov Approximating Node Connectivity Problems
via Set Covers . . . . . . . . . . . . . 75--92
Ross M. McConnell Linear-Time Recognition of Circular-Arc
Graphs . . . . . . . . . . . . . . . . . 93--147
Francis Y. L. Chin and
Stanley P. Y. Fung Online Scheduling with Partial Job
Values: Does Timesharing or
Randomization Help? . . . . . . . . . . 149--164
Vladimir Yanovski and
Israel A. Wagner and
Alfred M. Bruckstein A Distributed Ant Algorithm for
Efficiently Patrolling a Network . . . . 165--186
Magnús M. Halldórsson and
Guy Kortsarz and
Hadas Shachnai Sum coloring interval and $k$-claw free
graphs with application to scheduling
dependent jobs . . . . . . . . . . . . . 187--209
Sergio Cabello and
Marc van Kreveld Approximation Algorithms for Aligning
Points . . . . . . . . . . . . . . . . . 211--232
Mauricio Ayala-Rincón and
Paulo D. Conejo A linear time lower bound on McCreight
and general updating algorithms for
suffix trees . . . . . . . . . . . . . . 233--241
Enrico Angelelli and
Maria Grazia Speranza and
Zsolt Tuza Semi-On-line Scheduling on Two Parallel
Processors with an Upper Bound on the
Items . . . . . . . . . . . . . . . . . 243--262
Naoki Abe and
Alan W. Biermann and
Philip M. Long Reinforcement Learning with Immediate
Rewards and Linear Hypotheses . . . . . 263--293
Allan Borodin and
Morten N. Nielsen and
Charles Rackoff (Incremental) priority algorithms . . . 295--326
Daniel Kobler and
Udi Rotics Finding Maximum Induced Matchings in
Subclasses of Claw-Free and $P_5$-Free
Graphs, and in Graphs with Matching and
Induced Matching of Equal Maximum Size 327--346
Remco C. Veltkamp Shape Algorithmics . . . . . . . . . . . 1--4
Ulrich Eckhardt and
Helene Reiter Polygonal Representations of Digital
Sets . . . . . . . . . . . . . . . . . . 5--23
Isabelle Sivignon and
Florent Dupont and
Jean-Marc Chassery Decomposition of a Three-Dimensional
Discrete Object Surface into Discrete
Plane Pieces . . . . . . . . . . . . . . 25--43
Helmut Alt and
Christian Knauer and
Carola Wenk Comparison of Distance Measures for
Planar Curves . . . . . . . . . . . . . 45--58
Martin Gavrilov and
Piotr Indyk and
Rajeev Motwani and
Suresh Venkatasubramanian Combinatorial and Experimental Methods
for Approximate Point Pattern Matching 59--90
Bodo Rosenhahn and
Christian Perwass and
Gerald Sommer Free-Form Pose Estimation by Using Twist
Representations . . . . . . . . . . . . 91--113
L. Paul Chew and
Klara Kedem Finding the Consensus Shape for a
Protein Family . . . . . . . . . . . . . 115--129
Ovidiu Daescu New Results on Path Approximation . . . 131--143
Alon Efrat and
Frank Hoffmann and
Christian Knauer and
Klaus Kriegel and
Günter Rote and
Carola Wenk Covering with Ellipses . . . . . . . . . 145--160
Prosenjit Bose and
Pat Morin Testing the Quality of Manufactured
Disks and Balls . . . . . . . . . . . . 161--177
Tamal K. Dey and
Wulue Zhao Approximating the Medial Axis from the
Vorono\uì Diagram with a Convergence
Guarantee . . . . . . . . . . . . . . . 179--200
Michael Kazhdan and
Bernard Chazelle and
David Dobkin and
Thomas Funkhouser and
Szymon Rusinkiewicz A Reflective Symmetry Descriptor for 3D
Models . . . . . . . . . . . . . . . . . 201--225
Michela Mortara and
Giuseppe Patan\`e and
Michela Spagnuolo and
Bianca Falcidieno and
Jarek Rossignac Blowing Bubbles for Multi-Scale Analysis
and Decomposition of Triangle Meshes . . 227--248
Valerio Pascucci and
Kree Cole-McLaughlin Parallel Computation of the Topology of
Level Sets . . . . . . . . . . . . . . . 249--268
Tadao Takaoka Foreword . . . . . . . . . . . . . . . . 269--270
Xiao Zhou and
Takao Nishizeki Multicolorings of Series-Parallel Graphs 271--297
Danny Z. Chen and
Xiadong Wu Efficient algorithms for $k$-terminal
cuts on planar graphs . . . . . . . . . 299--316
David Bremner and
Ferran Hurtado and
Suneeta Ramaswami and
Vera Sacristán Small Strictly Convex Quadrilateral
Meshes of Point Sets . . . . . . . . . . 317--339
Sheung-Hung Poon and
Chan-Su Shin and
Tycho Strijk and
Takeaki Uno and
Alexander Wolff Labeling Points with Weights . . . . . . 341--362
Rudolf Fleischer and
Hisashi Koga Balanced Scheduling toward Loss-Free
Packet Queuing and Delay Fairness . . . 363--376
Gerth Stòlting Brodal and
Rolf Fagerberg and
Christian N. S. Pedersen Computing the Quartet Distance between
Evolutionary Trees in Time $O(n \log n)$ 377--395
Xuemin Lin Delay Optimization in Quorum Consensus 397--413
Klaus Jansen and
Samir Khuller Guest Editors' Introduction . . . . . . 415--416
Refael Hassin and
R. Ravi and
F. Sibel Salman Approximation Algorithms for a
Capacitated Network Design Problem . . . 417--431
Kamal Jain and
Vijay V. Vazirani An Approximation Algorithm for the Fault
Tolerant Metric Facility Location
Problem . . . . . . . . . . . . . . . . 433--439
Jochen Könemann and
Goran Konjevod and
Ojas Parekh and
Amitabh Sinha Improved Approximations for Tour and
Tree Covers . . . . . . . . . . . . . . 441--449
Venkatesan Guruswami Inapproximability Results for Set
Splitting and Satisfiability Problems
with No Mixed Clauses . . . . . . . . . 451--469
Martin Dyer and
Leslie Ann Goldberg and
Catherine Greenhill and
Mark Jerrum The Relative Complexity of Approximate
Counting Problems . . . . . . . . . . . 471--500
Sándor P. Fekete and
Henk Meijer Maximum Dispersion and Geometric Maximum
Weight Cliques . . . . . . . . . . . . . 501--511
Xiaotie Deng and
Haodi Feng and
Pixing Zhang and
Yuzhong Zhang and
Hong Zhu Minimizing Mean Completion Time in a
Batch Processing System . . . . . . . . 513--528
Mao-cheng Cai and
Xiaotie Deng and
Lusheng Wang Minimum $k$ arborescences with bandwidth
constraints . . . . . . . . . . . . . . 529--537
Zhi-Zhong Chen and
Xin He Disk Embeddings of Planar Graphs . . . . 539--576
Michael J. Spriggs and
J. Mark Keil and
Sergei Bespamyatnikh and
Michael Segal and
Jack Snoeyink Computing a $(1+\epsilon)$-Approximate
Geometric Minimum-Diameter Spanning Tree 577--589
Fréderic Chazal and
Véronique Maume-Deschamps and
Brigitte Vallée Erratum to: ``Dynamical sources in
information theory: fundamental
intervals and word prefixes''
[Algorithmica \bf 29 (2001), no. 1--2,
262--306; MR1887307] by Vallée . . . . . 591--596
Rajiv Gandhi and
Samir Khuller and
Yoo-Ah Kim and
Yung-Chun (Justin) Wan Algorithms for Minimizing Response Time
in Broadcast Scheduling . . . . . . . . 597--608
Tetsuo Shibuya Generalization of a Suffix Tree for RNA
Structural Pattern Matching . . . . . . 1--19
Charles Martel and
Glen Nuckolls and
Premkumar Devanbu and
Michael Gertz and
April Kwong and
Stuart G. Stubblebine A General Model for Authenticated Data
Structures . . . . . . . . . . . . . . . 21--41
Leah Epstein and
Ji\vr\'\i Sgall Approximation Schemes for Scheduling on
Uniformly Related and Identical Parallel
Machines . . . . . . . . . . . . . . . . 43--57
Klaus Jansen Scheduling Malleable Parallel Tasks: An
Asymptotic Fully Polynomial Time
Approximation Scheme . . . . . . . . . . 59--81
Petko Yanev and
Paolo Foschi and
Erricos John Kontoghiorghes Algorithms for Computing the QR
Decomposition of a Set of Matrices with
Common Columns . . . . . . . . . . . . . 83--93
Stavros D. Nikolopoulos and
Leonidas Palios Algorithms for $P_4$-Comparability Graph
Recognition and Acyclic $P_4$-Transitive
Orientation . . . . . . . . . . . . . . 95--126
John H. Reif and
Zheng Sun Movement Planning in the Presence of
Flows . . . . . . . . . . . . . . . . . 127--153
Chung Keung Poon and
Pixing Zhang Minimizing Makespan in Batch Machine
Scheduling . . . . . . . . . . . . . . . 155--174
Esther M. Arkin and
Refael Hassin and
Shlomi Rubinstein and
Maxim Sviridenko Approximations for Maximum
Transportation with Permutable Supply
Vector and Other Capacitated Star
Packing Problems . . . . . . . . . . . . 175--187
Ravindra K. Ahuja and
Dorit S. Hochbaum and
James B. Orlin A Cut-Based Algorithm for the Nonlinear
Dual of the Minimum Cost Network Flow
Problem . . . . . . . . . . . . . . . . 189--208
Petr Kolman and
Christian Scheideler Simple On-Line Algorithms for the
Maximum Disjoint Paths Problem . . . . . 209--233
David R. Wood Minimising the Number of Bends and
Volume in $3$-Dimensional Orthogonal
Graph Drawings with a Diagonal Vertex
Layout . . . . . . . . . . . . . . . . . 235--253
Jianjun Zhou and
Martin Müller Solving Systems of Difference
Constraints Incrementally with
Bidirectional Search . . . . . . . . . . 255--274
Adam L. Buchsbaum and
Michael T. Goodrich Three-Dimensional Layers of Maxima . . . 275--286
Anne Berry and
Jean R. S. Blair and
Pinar Heggernes and
Barry W. Peyton Maximum Cardinality Search for Computing
Minimal Triangulations of Graphs . . . . 287--298
Björn Brodén and
Mikael Hammar and
Bengt J. Nilsson Online and Offline Algorithms for the
Time-Dependent TSP with Time Zones . . . 299--319
Jens Gramm and
Jiong Guo and
Falk Hüffner and
Rolf Niedermeier Automated Generation of Search Tree
Algorithms for Hard Graph Modification
Problems . . . . . . . . . . . . . . . . 321--347
Mirela Damian and
Sriram V. Pemmaraju Computing Optimal Diameter-Bounded
Polygon Partitions . . . . . . . . . . . 1--14
Vida Dujmovi\'c and
Sue Whitesides An Efficient Fixed Parameter Tractable
Algorithm for $1$-Sided Crossing
Minimization . . . . . . . . . . . . . . 15--31
Giovanni Manzini and
Paolo Ferragina Engineering a Lightweight Suffix Array
Construction Algorithm . . . . . . . . . 33--50
Franziska Berger and
Peter Gritzmann and
Sven de Vries Minimum Cycle Bases for Network Graphs 51--62
Evanthia Papadopoulou The Hausdorff Voronoi diagram of point
clusters in the plane . . . . . . . . . 63--82
Jianer Chen and
Donald K. Friesen and
Weijia Jia and
Iyad A. Kanj Using Nondeterminism to Design Efficient
Deterministic Algorithms . . . . . . . . 83--97
Yih-En Andrew Ban and
Sergey Bereg and
Nabil H. Mustafa A Conjecture on Wiener Indices in
Combinatorial Chemistry . . . . . . . . 99--117
Enrico Nardelli and
Guido Proietti and
Peter Widmayer Nearly Linear Time Minimum Spanning Tree
Maintenance for Transient Node Failures 119--132
Marcin Peczarski New Results in Minimum-Comparison
Sorting . . . . . . . . . . . . . . . . 133--145
Alon Efrat and
Piotr Indyk and
Suresh Venkatasubramanian Pattern Matching for Sets of Segments 147--160
Jianbo Qian and
Cao An Wang A Linear-Time Approximation Scheme for
Maximum Weight Triangulation of Convex
Polygons . . . . . . . . . . . . . . . . 161--172
Yoshiharu Kohayakawa and
Flavio Keidi Miyazawa and
Prabhakar Raghavan and
Yoshiko Wakabayashi Multidimensional Cube Packing . . . . . 173--187
Sanjeev Arora and
Kevin Chang Approximation Schemes for
Degree-Restricted MST and Red--Blue
Separation Problems . . . . . . . . . . 189--210
Erik D. Demaine and
Mohammad Taghi Hajiaghayi Diameter and Treewidth in Minor-Closed
Graph Families, Revisited . . . . . . . 211--215
Stefano Leonardi Special issue: Selected papers from the
5th international workshop on
approximation algorithms for
combinatorial optimization and 10th
annual European symposium on algorithms,
Rome, Italy, September 16--21, 2002, and
20th annual symposium on theoretical
aspects of computer science (STAC 2003),
Berlin, Germany, February 27--March 1,
2003 . . . . . . . . . . . . . . . . . . 217--218
Uriel Feige and
László Lovász and
Prasad Tetali Approximating Min Sum Set Cover . . . . 219--234
Micha\l Ma\lafiejski and
Krzysztof Giaro and
Robert Janczewski and
Marek Kubale Sum Coloring of Bipartite Graphs with
Bounded Degree . . . . . . . . . . . . . 235--244
Chaitanya Swamy and
Amit Kumar Primal--Dual Algorithms for Connected
Facility Location Problems . . . . . . . 245--269
Spyros Angelopoulos and
Allan Borodin The Power of Priority Algorithms for
Facility Location and Set Cover . . . . 271--291
Liane Lewin-Eytan and
Joseph (Seffi) Naor and
Ariel Orda Admission Control in Networks with
Advance Reservations . . . . . . . . . . 293--304
Nikhil Bansal and
Kedar Dhamdhere and
Jochen Könemann and
Amitabh Sinha Non-Clairvoyant Scheduling for
Minimizing Mean Slowdown . . . . . . . . 305--318
Maarten Lipmann and
Xiwen Lu and
Willem E. de Paepe and
Rene A. Sitters and
Leen Stougie On-Line Dial-a-Ride Problems Under a
Restricted Information Model . . . . . . 319--329
Irene Finocchi and
Alessandro Panconesi and
Riccardo Silvestri An Experimental Analysis of Simple,
Distributed Vertex Coloring Algorithms 1--23
Joan Feigenbaum and
Sampath Kannan and
Jian Zhang Computing Diameter in the Streaming and
Sliding-Window Models . . . . . . . . . 25--41
Refael Hassin and
Asaf Levin Approximation Algorithms for Quickest
Spanning Tree Problems . . . . . . . . . 43--52
Guoliang Xue and
Wei Xiao A Polynomial Time Approximation Scheme
for Minimum Cost Delay-Constrained
Multicast Tree under a Steiner Topology 53--72
Fedor V. Fomin and
Pinar Heggernes and
Jan Arne Telle Graph Searching, Elimination Trees, and
a Generalization of Bandwidth . . . . . 73--87
Gonzalo Navarro and
Mathieu Raffinot New Techniques for Regular Expression
Searching . . . . . . . . . . . . . . . 89--116
Jochen Könemann and
Asaf Levin and
Amitabh Sinha Approximating the Degree-Bounded Minimum
Diameter Spanning Tree Problem . . . . . 117--129
Cees Duin A Branch-Checking Algorithm for
All-Pairs Shortest Paths . . . . . . . . 131--145
Sariel Har-Peled and
Soham Mazumdar Fast algorithms for computing the
smallest $k$-enclosing circle . . . . . 147--157
Vladlen Koltun and
Carola Wenk Matching Polyhedral Terrains Using
Overlays of Envelopes . . . . . . . . . 159--183
Sariel Har-Peled and
Bardia Sadri How fast is the $k$-means method? . . . 185--202
Heikki Hyyrö and
Gonzalo Navarro Bit-Parallel Witnesses and Their
Applications to Approximate String
Matching . . . . . . . . . . . . . . . . 203--231
Paz Carmi and
Shlomi Dolev and
Sariel Har-Peled and
Matthew J. Katz and
Michael Segal Geographic Quorum System Approximations 233--244
Erik D. Demaine and
Mohammadtaghi Hajiaghayi and
Dimitrios M. Thilikos Exponential Speedup of Fixed-Parameter
Algorithms for Classes of Graphs
Excluding Single-Crossing Graphs as
Minors . . . . . . . . . . . . . . . . . 245--267
Sorina Dumitrescu and
Xiaolin Wu Optimal Two-Description Scalar Quantizer
Design . . . . . . . . . . . . . . . . . 269--287
Carsten Gutwenger and
Petra Mutzel and
René Weiskircher Inserting an Edge into a Planar Graph 289--308
Yi-Jen Chiang New Approximation Results for the
Maximum Scatter TSP . . . . . . . . . . 309--341
Prosenjit Bose and
Pat Morin Guest Editors' Foreword . . . . . . . . 1--2
John Iacono Key-Independent Optimality . . . . . . . 3--10
Luc Devroye Universal Asymptotics for Random Tries
and PATRICIA Trees . . . . . . . . . . . 11--29
Amitabha Bagchi and
Adam L. Buchsbaum and
Michael T. Goodrich Biased Skip Lists . . . . . . . . . . . 31--48
John Iacono and
Stefan Langerman Queaps . . . . . . . . . . . . . . . . . 49--56
Jason D. Hartline and
Edwin S. Hong and
Alexander E. Mohr and
William R. Pentney and
Emily C. Rocke Characterizing History Independent Data
Structures . . . . . . . . . . . . . . . 57--74
Sumanta Guha and
Son Dinh Tran Reconstructing Curves without Delaunay
Computation . . . . . . . . . . . . . . 75--94
Hiroshi Fujiwara and
Kazuo Iwama Average-Case Competitive Analyses for
Ski-Rental Problems . . . . . . . . . . 95--107
Marek Karpinski and
Ion I. M\uandoiu and
Alexander Olshevsky and
Alexander Zelikovsky Improved Approximation Algorithms for
the Quality of Service Multicast Tree
Problem . . . . . . . . . . . . . . . . 109--120
Markus Bläser and
Bodo Manthey Approximating Maximum Weight Cycle
Covers in Directed Graphs with Weights
Zero and One . . . . . . . . . . . . . . 121--139
Ken'ichiro Ohta and
Kunihiko Sadakane and
Akiyoshi Shioura and
Takeshi Tokuyama A fast, accurate, and simple method for
pricing European-Asian and saving-Asian
options . . . . . . . . . . . . . . . . 141--158
Seok-Hee Hong and
Peter Eades Drawing planar graphs symmetrically. II.
Biconnected planar graphs . . . . . . . 159--197
Rolf Mohring and
Rajeev Raman Preface . . . . . . . . . . . . . . . . 199--201
Pankaj K. Agarwal and
Sariel Har-Peled and
Nabil H. Mustafa and
Yusu Wang Near-Linear Time Approximation
Algorithms for Curve Simplification . . 203--219
Pankaj K. Agarwal and
Cecilia M. Procopiuc and
Kasturi R. Varadarajan Approximation algorithms for a $k$-line
center . . . . . . . . . . . . . . . . . 221--230
Georg Baier and
Ekkehard Köhler and
Martin Skutella The $k$-splittable flow problem . . . . 231--248
Prosenjit Bose and
Joachim Gudmundsson and
Michiel Smid Constructing Plane Spanners of Bounded
Degree and Low Weight . . . . . . . . . 249--264
Danny Z. Chen and
Xiaobo S. Hu and
Shuang Luan and
Xiaodong Wu and
Cedric X. Yu Optimal Terrain Construction Problems
and Applications in Intensity-Modulated
Radiation Therapy . . . . . . . . . . . 265--288
Kirk R. Pruhs and
Patchrawat Uthaisombut A Comparison of Multicast Pull Models 289--307
Hadas Shachnai and
Tami Tamir and
Gerhard J. Woeginger Minimizing Makespan and Preemption Costs
on a System of Uniform Machines . . . . 309--334
Lisa Zhang Guest Editor's Introduction . . . . . . 1--3
Ashish Goel and
Deborah Estrin Simultaneous Optimization for Concave
Costs: Single Sink Aggregation or Single
Source Buy-at-Bulk . . . . . . . . . . . 5--15
Chandra Chekuri and
A. Gupta and
Amit Kumar and
J. Naor and
Danny Raz Building Edge-Failure Resilient Networks 17--41
Thomas Erlebach and
Stamatis Stefanakos Wavelength Conversion in All-Optical
Networks with Shortest-Path Routing . . 43--61
Alex Kesselman and
Yishay Mansour and
Rob van Stee Improved competitive guarantees for QoS
buffering . . . . . . . . . . . . . . . 63--80
Yossi Azar and
Yossi Richter Management of multi-queue switches in
QoS networks . . . . . . . . . . . . . . 81--96
Alex Kesselman and
Yishay Mansour Adaptive AIMD Congestion Control . . . . 97--111
Jessica H. Fong and
Anna C. Gilbert and
Sampath Kannan and
Martin J. Strauss Better Alternatives to OSPF Routing . . 113--131
Jay Sethuraman and
Chung-Piaw Teo Effective Routing and Scheduling in
Adversarial Queueing Networks . . . . . 133--146
Zhi-Zhong Chen and
Mitsuharu Kouno A Linear-Time Algorithm for $7$-Coloring
$1$-Plane Graphs . . . . . . . . . . . . 147--177
Nadav Efraty and
Gad M. Landau Sparse Normalized Local Alignment . . . 179--194
Ho Kyung Kim and
Leonidas J. Guibas and
Sung Yong Shin Efficient Collision Detection among
Moving Spheres with Unknown Trajectories 195--210
Olgica Milenkovic and
Kevin J. Compton Average Case Analysis of Gosper's
Algorithm for a Class of Urn Model
Inputs . . . . . . . . . . . . . . . . . 211--244
Jianer Chen and
Iyad A. Kanj and
Ge Xia Labeled Search Trees and Amortized
Analysis: Improved Upper Bounds for
NP-Hard Problems . . . . . . . . . . . . 245--273
David Benoit and
Erik D. Demaine and
J. Ian Munro and
Rajeev Raman and
Venkatesh Raman and
S. Srinivasa Rao Representing Trees of Higher Degree . . 275--292
Jesper Jansson and
Joseph H.-K. Ng and
Kunihiko Sadakane and
Wing-Kin Sung Rooted Maximum Agreement Supertrees . . 293--307
Mahesh Kallahalla and
Peter J. Varman Optimal Read-Once Parallel Disk
Scheduling . . . . . . . . . . . . . . . 309--343
Peter Eades and
Qingwen Feng and
Xuemin Lin and
Hiroshi Nagamochi Straight-Line Drawing Algorithms for
Hierarchical Graphs and Clustered Graphs 1--32
Peter Damaschke Multiple Spin-Block Decisions . . . . . 33--48
Yossi Azar and
Oded Regev Combinatorial Algorithms for the
Unsplittable Flow Problem . . . . . . . 49--66
Seok-Hee Hong and
Peter Eades Drawing Planar Graphs Symmetrically,
III: Oneconnected Planar Graphs . . . . 67--100
Naoki Katoh Foreword . . . . . . . . . . . . . . . . 101--101
Jinhee Chun and
Kunihiko Sadakane and
Takeshi Tokuyama Linear Time Algorithm for Approximating
a Curve by a Single-Peaked Curve . . . . 103--115
Jae-Sook Cheong and
Herman J. Haverkort and
A. Frank van der Stappen Computing All Immobilizing Grasps of a
Simple Polygon with Few Contacts . . . . 117--136
Annette Ebbers-Baumann and
Ansgar Grune and
Rolf Klein The Geometric Dilation of Finite Point
Sets . . . . . . . . . . . . . . . . . . 137--149
Anil Maheshwari and
Michiel Smid A Dynamic Dictionary for Priced
Information with Application . . . . . . 151--165
Erik D. Demaine and
Stefan Langerman and
Joseph O'Rourke Geometric Restrictions on Producible
Polygonal Protein Chains . . . . . . . . 167--181
Mark Huber Exact Sampling from Perfect Matchings of
Dense Regular Bipartite Graphs . . . . . 183--193
Xujin Chen and
Wenan Zang An Efficient Algorithm for Finding
Maximum Cycle Packings in Reducible Flow
Graphs . . . . . . . . . . . . . . . . . 195--211
Zeev Nutov Approximating Rooted Connectivity
Augmentation Problems . . . . . . . . . 213--231
Therese Biedl and
Torsten Thiele and
David R. Wood Three-Dimensional Orthogonal Graph
Drawing with Optimal Volume . . . . . . 233--255
Toshimasa Ishii and
Hiroshi Nagamochi and
Toshihide Ibaraki Augmenting a $(k-1)$-Vertex-Connected
Multigraph $l$-Edge-Connected and
$k$-Vertex-Connected Multigraph . . . . 257--280
M. Brazil and
D. A. Thomas and
J. F. Weng and
M. Zachariasen Canonical Forms and Algorithms for
Steiner Trees in Uniform Orientation
Metrics . . . . . . . . . . . . . . . . 281--300
Ashish Goel and
Adam Meyerson Simultaneous Optimization via
Approximate Majorization for Concave
Profits or Convex Costs . . . . . . . . 301--323
Hee-Kap Ahn and
Siu-Wing Cheng and
Otfried Cheong Casting with Skewed Ejection Direction 325--342
Hajo Broersma and
Fedor V. Fomin and
Jan Kratochvil and
Gerhard J. Woeginger Planar Graph Coloring Avoiding
Monochromatic Subgraphs: Trees and Paths
Make It Difficult . . . . . . . . . . . 343--361
Michael Dom and
Jiong Guo and
Falk Huffner and
Rolf Niedermeier Error Compensation in Leaf Power
Problems . . . . . . . . . . . . . . . . 363--381
Susanne Albers and
Tomasz Radzik Foreword . . . . . . . . . . . . . . . . 1--2
Marcin Mucha and
Piotr Sankowski Maximum matchings in planar graphs via
Gaussian elimination . . . . . . . . . . 3--20
Joseph Cheriyan and
Mohammad R. Salavatipour Hardness and approximation results for
packing Steiner trees . . . . . . . . . 21--43
Costas Busch and
Malik Magdon-Ismail and
Marios Mavronicolas and
Paul Spirakis Direct routing: Algorithms and
complexity . . . . . . . . . . . . . . . 45--68
Yossi Azar and
Arik Litichevskey Maximizing throughput in multi-queue
switches . . . . . . . . . . . . . . . . 69--90
Marc van Kreveld and
A. Frank van der Stappen Approximate unions of lines and
minkowski sums . . . . . . . . . . . . . 91--107
Amihood Amir and
Estrella Eisenberg and
Ely Porat Swap and mismatch edit distance . . . . 109--120
Rene Beier and
Berthold Vöcking An experimental study of random knapsack
problems . . . . . . . . . . . . . . . . 121--136
Leana Golubchik and
Samir Khuller and
Yoo-Ah Kim and
Svetlana Shargorodskaya and
Yung-Chun (Justin) Wan Data migration on parallel disks:
Algorithms and evaluation . . . . . . . 137--158
Vida Dujmovic and
Michael Fellows and
Michael Hallett and
Matthew Kitching and
Giuseppe Liotta and
Catherine McCartin and
Naomi Nishimura and
Prabhakar Ragde and
Fran Rosamond and
Matthew Suderman and
Sue Whitesides and
David R. Wood A Fixed-Parameter Approach to 2-Layer
Planarization . . . . . . . . . . . . . 159--182
Zvika Brakerski and
Aviv Nisgav and
Boaz Patt-Shamir General Perfectly Periodic Scheduling 183--208
Victor Chepoi and
Bertrand Estellon and
Karim Nouioua and
Yann Vaxes Mixed Covering of Trees and the
Augmentation Problem with Odd Diameter
Constraints . . . . . . . . . . . . . . 209--226
Zhi-Zhong Chen and
Michelangelo Grigni and
Christos H. Papadimitriou Recognizing Hole-Free 4-Map Graphs in
Cubic Time . . . . . . . . . . . . . . . 227--262
Frank Dehne Guest Editor's Introduction . . . . . . 263--267
Faisal N. Abu-Khzam and
Michael A. Langston and
Pushkar Shanbhag and
Christopher T. Symons Scalable Parallel Algorithms for FPT
Problems . . . . . . . . . . . . . . . . 269--284
Thomas M. Keane and
Andrew J. Page and
Thomas J. Naughton and
Simon A. A. Travers and
James O. McInerney Building Large Phylogenetic Trees on
Coarse-Grained Parallel Machines . . . . 285--300
Carlos E. R. Alves and
Edson N. Caceres and
Siang Wun Song A Coarse-Grained Parallel Algorithm for
the All-Substrings Longest Common
Subsequence Problem . . . . . . . . . . 301--335
Adrian Driga and
Paul Lu and
Jonathan Schaeffer and
Duane Szafron and
Kevin Charter and
Ian Parsons FastLSA: A Fast, Linear-Space, Parallel
and Sequential Algorithm for Sequence
Alignment . . . . . . . . . . . . . . . 337--375
Jie Chi and
Mehmet Koyuturk and
Ananth Grama \sc ConQuest: A Coarse-Grained Algorithm
for Constructing Summaries of
Distributed Discrete Datasets . . . . . 377--401
James Chilson and
Raymond Ng and
Alan Wagner and
Ruben Zamar Parallel Computation of High-Dimensional
Robust Correlation and Covariance
Matrices . . . . . . . . . . . . . . . . 403--431
Jerffeson Teixeira de Souza and
Stan Matwin and
Nathalie Japkowicz Parallelizing Feature Selection . . . . 433--456
Mehul Bhatt and
Andrew Flahive and
Carlo Wouters and
Wenny Rahayu and
David Taniar MOVE: A Distributed Framework for
Materialized Ontology View Extraction 457--481
Geeta Chaudhry and
Thomas H. Cormen Slabpose Columnsort: A New Oblivious
Algorithm for Out-of-Core Sorting on
Distributed-Memory Clusters . . . . . . 483--508
Emilio Di Giacomo and
Walter Didimo and
Giuseppe Liotta and
Stephen K. Wismath Book Embeddability of Series-Parallel
Digraphs . . . . . . . . . . . . . . . . 531--547
Rudolf Fleischer and
Mordecai J. Golin and
Yan Zhang Online Maintenance of $k$-Medians and
$k$-Covers on a Line . . . . . . . . . . 549--567
Michael Elkin and
Guy Kortsarz An Approximation Algorithm for the
Directed Telephone Multicast Problem . . 569--583
Sathish Govindarajan and
Tamas Lukovszki and
Anil Maheshwari and
Norbert Zeh I/O-Efficient Well-Separated Pair
Decomposition and Applications . . . . . 585--614
Rudolf Fleischer Foreword . . . . . . . . . . . . . . . . 1--1
Kazuyuki Amano and
Akira Maruoka The Monotone Circuit Complexity of
Quadratic Boolean Functions . . . . . . 3--14
Amitai Armon and
Uri Zwick Multicriteria Global Minimum Cuts . . . 15--26
Fredrik Bengtsson and
Jingsen Chen Efficient Algorithms for k Maximum Sums 27--41
Jin-Yi Cai and
Osamu Watanabe Random Access to Advice Strings and
Collapsing Results . . . . . . . . . . . 43--57
Qi Cheng and
Ming-Deh Huang Partial Lifting and the Elliptic Curve
Discrete Logarithm Problem . . . . . . . 59--68
Anders Dessmark and
Pierre Fraigniaud and
Dariusz R. Kowalski and
Andrzej Pelc Deterministic Rendezvous in Graphs . . . 69--96
John Hershberger and
Nisheeth Shrivastava and
Subhash Suri and
Csaba D. Toth Adaptive Spatial Partitioning for
Multidimensional Data Streams . . . . . 97--117
Timo von Oertzen Exact Computation of Polynomial Zeros
Expressible by Square Roots . . . . . . 119--136
Joachim von zur Gathen and
Igor E. Shparlinski GCD of Random Linear Combinations . . . 137--148
Celina M. H. de Figueiredo and
Guilherme D. da Fonseca and
Vinicius G. P. de Sa and
Jeremy Spinrad Algorithms for the Homogeneous Set
Sandwich Problem . . . . . . . . . . . . 149--180
Uri Zwick A Slightly Improved Sub-Cubic Algorithm
for the All Pairs Shortest Paths Problem
with Real Edge Lengths . . . . . . . . . 181--192
Esther M. Arkin and
Michael A. Bender and
Sandor P. Fekete and
Joseph S. B. Mitchell and
Martin Skutella The Freeze-Tag Problem: How to Wake Up a
Swarm of Robots . . . . . . . . . . . . 193--221
Jesper Jansson and
See-Kiong Ng and
Wing-Kin Sung and
Hugo Willy A Faster and More Space-Efficient
Algorithm for Inferring Arc-Annotations
of RNA Sequences through Alignment . . . 223--245
Philippe Jacquet and
Daniel Panario and
Wojciech Szpankowski Preface . . . . . . . . . . . . . . . . 247--248
Roberto M. Avanzi and
Clemens Heuberger and
Helmut Prodinger Scalar Multiplication on Koblitz Curves
Using the Frobenius Endomorphism and Its
Combination with Point Halving:
Extensions and Mathematical Analysis . . 249--270
Nicolas Broutin and
Luc Devroye Large Deviations for the Weighted Height
of an Extended Class of Trees . . . . . 271--297
Brigitte Chauvin and
Michael Drmota The Random Multisection Problem,
Travelling Waves and the Distribution of
the Height of $m$-Ary Search Trees . . . 299--327
Sylvie Corteel and
William M. Y. Goh and
Pawel Hitczenko A Local Limit Theorem in the Theory of
Overpartitions . . . . . . . . . . . . . 329--343
James Allen Fill and
Nevin Kapur and
Alois Panholzer Destruction of Very Simple Trees . . . . 345--366
Michael Fuchs and
Hsien-Kuei Hwang and
Ralph Neininger Profiles of Random Trees: Limit Theorems
for Random Recursive Trees and Binary
Search Trees . . . . . . . . . . . . . . 367--407
Jennie C. Hansen and
Eric Schmutz and
Li Sheng The Expected Size of the Rule $k$
Dominating Set . . . . . . . . . . . . . 409--418
Svante Janson Left and Right Pathlengths in Random
Binary Trees . . . . . . . . . . . . . . 419--429
Guy Louchard and
Helmut Prodinger Asymptotics of the Moments of
Extreme-Value Related Distribution
Functions . . . . . . . . . . . . . . . 431--467
Lars Arge and
Darren Erik Vengroff and
Jeffrey Scott Vitter External-Memory Algorithms for
Processing Line Segments in Geographic
Information Systems . . . . . . . . . . 1--25
Andreas Brandstadt and
Feodor F. Dragan and
Hoang-Oanh Le and
Van Bang Le and
Ryuhei Uehara Tree Spanners for Bipartite Graphs and
Probe Interval Graphs . . . . . . . . . 27--51
Amit Chakrabarti and
Chandra Chekuri and
Anupam Gupta and
Amit Kumar Approximation Algorithms for the
Unsplittable Flow Problem . . . . . . . 53--78
Subhash Suri and
Csaba D. Toth and
Yunhong Zhou Selfish Load Balancing and Atomic
Congestion Games . . . . . . . . . . . . 79--96
Leszek Gasieniec and
Aris Pagourtzis and
Igor Potapov and
Tomasz Radzik Deterministic Communication in Radio
Networks with Large Labels . . . . . . . 97--117
Stavros D. Nikolopoulos and
Leonidas Palios Detecting Holes and Antiholes in Graphs 119--138
Frank van den Eijkhof and
Hans L. Bodlaender and
M. C. A. Koster Safe Reduction Rules for Weighted
Treewidth . . . . . . . . . . . . . . . 139--158
Siu-Wing Cheng and
Antoine Vigneron Motorcycle Graphs and Straight Skeletons 159--182
Paz Carmi and
Matthew J. Katz Power Assignment in Radio Networks with
Two Power Levels . . . . . . . . . . . . 183--201
Paolo D'Alberto and
Alexandru Nicolau R-Kleene: A High-Performance
Divide-and-Conquer Algorithm for the
All-Pair Shortest Path for Densely
Connected Networks . . . . . . . . . . . 203--213
Alessandro Panconesi Foreword . . . . . . . . . . . . . . . . 215--215
Udo Adamy and
Christoph Ambuhl and
R. Sai Anand and
Thomas Erlebach Call Control in Rings . . . . . . . . . 217--238
Susanne Albers and
Rob van Stee A Study of Integrated Document and
Connection Caching in the WWW . . . . . 239--252
Nir Avrahami and
Yossi Azar Minimizing Total Flow Time and Total
Completion Time with Immediate
Dispatching . . . . . . . . . . . . . . 253--268
Thomas Erlebach and
Riko Jacob and
Matus Mihalak and
Marc Nunkesser and
Gabor Szabo and
Peter Widmayer An Algorithmic View on OVSF Code
Assignment . . . . . . . . . . . . . . . 269--298
Alex Hall and
Katharina Langkau and
Martin Skutella An FPTAS for Quickest Multicommodity
Flows with Inflow-Dependent Transit
Times . . . . . . . . . . . . . . . . . 299--321
Klaus Jansen and
Guochuan Zhang Maximizing the Total Profit of
Rectangles Packed into a Rectangle . . . 323--342
Joseph (Seffi) Naor and
Hadas Shachnai and
Tami Tamir Real-Time Scheduling with a Budget . . . 343--364
Janos Pach and
Farhad Shahrokhi Guest Editors' Foreword . . . . . . . . 365--365
Greg Aloupis and
Prosenjit Bose and
Pat Morin Reconfiguring Triangulations with Edge
Flips and Point Moves . . . . . . . . . 367--378
Reid Andersen and
Fan Chung and
Linyuan Lu No-Three-in-Line-in-$3$D . . . . . . . . 379--397
Reid Andersen and
Fan Chung and
Linyuan Lu Drawing Power Law Graphs Using a
Local/Global Decomposition . . . . . . . 397--397
Nicolas Bonichon and
Stefan Felsner and
Mohamed Mosbah Convex Drawings of $3$-Connected Plane
Graphs . . . . . . . . . . . . . . . . . 399--420
Robert B. Ellis and
Jeremy L. Martin and
Catherine Yan Random Geometric Graph Diameter in the
Unit Ball . . . . . . . . . . . . . . . 421--438
David Eppstein and
Michael T. Goodrich and
Jeremy Yu Meng Confluent Layered Drawings . . . . . . . 439--452
Hubert de Fraysseix and
Patrice Ossona de Mendez Representations by Contact and
Intersection of Segments . . . . . . . . 453--463
Peter Hui and
Michael J. Pelsmajer and
Marcus Schaefer and
Daniel Stefankovic Train Tracks and Confluent Drawings . . 465--479
Attila Por and
David R. Wood No-Three-in-Line-in-$3$D . . . . . . . . 481--488
Samir Khuller and
Yoo-Ah Kim Broadcasting in Heterogeneous Networks 1--21
Wing-Kai Hon and
Tak-Wah Lam and
Kunihiko Sadakane and
Wing-Kin Sung and
Siu-Ming Yiu A Space and Time Efficient Algorithm for
Constructing Compressed Suffix Arrays 23--36
Sven Verdoolaege and
Rachid Seghir and
Kristof Beyls and
Vincent Loechner and
Maurice Bruynooghe Counting Integer Points in Parametric
Polytopes Using Barvinok's Rational
Functions . . . . . . . . . . . . . . . 37--66
Stefan Dobrev and
Paola Flocchini and
Giuseppe Prencipe and
Nicola Santoro Mobile Search for a Black Hole in an
Anonymous Ring . . . . . . . . . . . . . 67--90
Marios Mavronicolas and
Paul Spirakis The Price of Selfish Routing . . . . . . 91--126
Lusheng Wang Foreword . . . . . . . . . . . . . . . . 127--127
Kamalika Chaudhuri and
Anshul Kothari and
Rudi Pendavingh and
Ram Swaminathan and
Robert Tarjan and
Yunhong Zhou Server Allocation Algorithms for Tiered
Systems . . . . . . . . . . . . . . . . 129--146
Fan Chung and
Ron Graham and
Jia Mao and
Andrew Yao Oblivious and Adaptive Strategies for
the Majority and Plurality Problems . . 147--157
Xiaotie Deng and
Li-Sha Huang and
Minming Li On Walrasian Price of CPU Time . . . . . 159--172
Joong Chae Na and
Raffaele Giancarlo and
Kunsoo Park On-Line Construction of Two-Dimensional
Suffix Trees in $O(n^2 \log n)$ Time . . 173--186
Miklos Csuros and
Bin Ma Rapid Homology Search with Neighbor
Seeds . . . . . . . . . . . . . . . . . 187--202
Jinsong Tan and
Kok Seng Chua and
Louxin Zhang and
Song Zhu Algorithmic and Complexity Issues of
Three Clustering Methods in Microarray
Data Analysis . . . . . . . . . . . . . 203--219
Frederic Magniez and
Ashwin Nayak Quantum Complexity of Testing Group
Commutativity . . . . . . . . . . . . . 221--232
Anders Dessmark and
Jesper Jansson and
Andrzej Lingas and
Eva-Marta Lundell Polynomial-Time Algorithms for the
Ordered Maximum Agreement Subtree
Problem . . . . . . . . . . . . . . . . 233--248
Colin Cooper and
Alan Frieze and
Gregory B. Sorkin Random $2$-SAT with Prescribed Literal
Degrees . . . . . . . . . . . . . . . . 249--265
Paola Bonizzoni A Linear-Time Algorithm for the Perfect
Phylogeny Haplotype Problem . . . . . . 267--285
Jinsong Tan and