Algorithmica

2005

Fast Algorithms for Computing the Smallest k-Enclosing Circle
by: Sariel Har-Peled, Soham Mazumdar v. 41 i. 3 p. 147 - 157
Matching Polyhedral Terrains Using Overlays of Envelopes
by: Vladlen Koltun, Carola Wenk v. 41 i. 3 p. 159 - 183
How Fast Is the k-Means Method?
by: Sariel Har-Peled, Bardia Sadri v. 41 i. 3 p. 185 - 202
Bit-Parallel Witnesses and Their Applications to Approximate String Matching
by: Heikki Hyyrö, Gonzalo Navarro v. 41 i. 3 p. 203 - 231
Geographic Quorum System Approximations
by: Paz Carmi, Shlomi Dolev, Sariel Har-Peled, Matthew J. Katz, Michael Segal v. 41 i. 4 p. 233 - 244
Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors
by: Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos v. 41 i. 4 p. 245 - 267
Optimal Two-Description Scalar Quantizer Design
by: Sorina Dumitrescu, Xiaolin Wu v. 41 i. 4 p. 269 - 287
Inserting an Edge into a Planar Graph
by: Carsten Gutwenger, Petra Mutzel, René Weiskircher v. 41 i. 4 p. 289 - 308
New Approximation Results for the Maximum Scatter TSP
by: Yi-Jen Chiang v. 41 i. 4 p. 309 - 341
Guest Editors' Foreword
by: Prosenjit Bose, Pat Morin v. 42 i. 1 p. 1 - 2
Key-Independent Optimality
by: John Iacono v. 42 i. 1 p. 3 - 10
Universal Asymptotics for Random Tries and PATRICIA Trees
by: Luc Devroye v. 42 i. 1 p. 11 - 29
Biased Skip Lists
by: Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich v. 42 i. 1 p. 31 - 48
Queaps
by: John Iacono, Stefan Langerman v. 42 i. 1 p. 49 - 56
Characterizing History Independent Data Structures
by: Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, Emily Rocke v. 42 i. 1 p. 57 - 74
Reconstructing Curves without Delaunay Computation
by: Sumanta Guha, Son Dinh Tran v. 42 i. 1 p. 75 - 94
Average-Case Competitive Analyses for Ski-Rental Problems
by: Hiroshi Fujiwara, Kazuo Iwama v. 42 i. 1 p. 95 - 107
Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem
by: Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky v. 42 i. 2 p. 109 - 120
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One
by: Markus Bläser, Bodo Manthey v. 42 i. 2 p. 121 - 139
A Fast, Accurate, and Simple Method for Pricing European-Asian and Saving-Asian Options
by: Kenichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura, Takeshi Tokuyama v. 42 i. 2 p. 141 - 158
Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs
by: Seok-Hee Hong, Peter Eades v. 42 i. 2 p. 159 - 197

2004

Minimizing Mean Completion Time in a Batch Processing System
by: Xiaotie Deng, Haodi Feng, Pixing Zhang, Yuzhong Zhang, Hong Zhu v. 38 i. 4 p. 513 - 528
Minimum k Arborescences with Bandwidth Constraints
by: Mao-cheng Cai, Xiaotie Deng, Lusheng Wang v. 38 i. 4 p. 529 - 537
Disk Embeddings of Planar Graphs
by: Zhi-Zhong Chen, Xin He v. 38 i. 4 p. 539 - 576
Computing a (1+epsilon)-Approximate Geometric Minimum-Diameter Spanning Tree
by: Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink v. 38 i. 4 p. 577 - 589
Erratum to 'Dynamical Sources in Information Theory: Fundamental Intervals and Word Prefixes'
by: Frédéric Chazal, Véronique Maume-Deschamps, Brigitte Vallée v. 38 i. 4 p. 591 - 596
Algorithms for Minimizing Response Time in Broadcast Scheduling
by: Rajiv Gandhi, Samir Khuller, Yoo Ah Kim, Yung-Chun (Justin) Wan v. 38 i. 4 p. 597 - 608
Generalization of a Suffix Tree for RNA Structural Pattern Matching
by: Tetsuo Shibuya v. 39 i. 1 p. 1 - 19
A General Model for Authenticated Data Structures
by: Charles U. Martel, Glen Nuckolls, Premkumar T. Devanbu, Michael Gertz, April Kwong, Stuart G. Stubblebine v. 39 i. 1 p. 21 - 41
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
by: Leah Epstein, Jiri Sgall v. 39 i. 1 p. 43 - 57
Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial Time Approximation Scheme
by: Klaus Jansen v. 39 i. 1 p. 59 - 81
Algorithms for Computing the QR Decomposition of a Set of Matrices with Common Columns
by: Petko Yanev, Paolo Foschi, Erricos John Kontoghiorghes v. 39 i. 1 p. 83 - 93
Algorithms for P4-Comparability Graph Recognition and Acyclic P4-Transitive Orientation
by: Stavros D. Nikolopoulos, Leonidas Palios v. 39 i. 2 p. 95 - 126
Movement Planning in the Presence of Flows
by: John H. Reif, Zheng Sun v. 39 i. 2 p. 127 - 153
Minimizing Makespan in Batch Machine Scheduling
by: Chung Keung Poon, Pixing Zhang v. 39 i. 2 p. 155 - 174
Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems
by: Esther M. Arkin, Refael Hassin, Shlomi Rubinstein, Maxim Sviridenko v. 39 i. 2 p. 175 - 187
A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem
by: Ravindra K. Ahuja, Dorit S. Hochbaum, James B. Orlin v. 39 i. 3 p. 189 - 208
Simple On-Line Algorithms for the Maximum Disjoint Paths Problem
by: Petr Kolman, Christian Scheideler v. 39 i. 3 p. 209 - 233
Minimising the Number of Bends and Volume in 3-Dimensional Orthogonal Graph Drawings with a Diagonal Vertex Layout
by: David R. Wood v. 39 i. 3 p. 235 - 253
Solving Systems of Difference Constraints Incrementally with Bidirectional Search
by: Jianjun Zhou, Martin Müller 0003 v. 39 i. 3 p. 255 - 274
Three-Dimensional Layers of Maxima
by: Adam L. Buchsbaum, Michael T. Goodrich v. 39 i. 4 p. 275 - 286
Maximum Cardinality Search for Computing Minimal Triangulations of Graphs
by: Anne Berry, Jean R. S. Blair, Pinar Heggernes, Barry W. Peyton v. 39 i. 4 p. 287 - 298
Online and Offline Algorithms for the Time-Dependent TSP with Time Zones
by: Björn Brodén, Mikael Hammar, Bengt J. Nilsson v. 39 i. 4 p. 299 - 319
Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems
by: Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier v. 39 i. 4 p. 321 - 347
Computing Optimal Diameter-Bounded Polygon Partitions
by: Mirela Damian, Sriram V. Pemmaraju v. 40 i. 1 p. 1 - 14
An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
by: Vida Dujmovic, Sue Whitesides v. 40 i. 1 p. 15 - 31
Engineering a Lightweight Suffix Array Construction Algorithm
by: Giovanni Manzini, Paolo Ferragina v. 40 i. 1 p. 33 - 50
Minimum Cycle Bases for Network Graphs
by: Franziska Berger, Peter Gritzmann, Sven de Vries v. 40 i. 1 p. 51 - 62
The Hausdorff Voronoi Diagram of Point Clusters in the Plane
by: Evanthia Papadopoulou v. 40 i. 2 p. 63 - 82
Using Nondeterminism to Design Efficient Deterministic Algorithms
by: Jianer Chen, Donald K. Friesen, Weijia Jia, Iyad A. Kanj v. 40 i. 2 p. 83 - 97
A Conjecture on Wiener Indices in Combinatorial Chemistry
by: Yih-En Andrew Ban, Sergey Bereg, Nabil H. Mustafa v. 40 i. 2 p. 99 - 117
Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures
by: Enrico Nardelli, Guido Proietti, Peter Widmayer v. 40 i. 2 p. 119 - 132
New Results in Minimum-Comparison Sorting
by: Marcin Peczarski v. 40 i. 2 p. 133 - 145
Pattern Matching for Sets of Segments
by: Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian v. 40 i. 3 p. 147 - 160
A Linear-Time Approximation Scheme for Maximum Weight Triangulation of Convex Polygons
by: Jianbo Qian, Cao An Wang v. 40 i. 3 p. 161 - 172
Multidimensional Cube Packing
by: Yoshiharu Kohayakawa, Flávio Keidi Miyazawa, Prabhakar Raghavan, Yoshiko Wakabayashi v. 40 i. 3 p. 173 - 187
Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems
by: Sanjeev Arora, Kevin L. Chang v. 40 i. 3 p. 189 - 210
Diameter and Treewidth in Minor-Closed Graph Families, Revisited
by: Erik D. Demaine, Mohammad Taghi Hajiaghayi v. 40 i. 3 p. 211 - 215
Preface
by: Stefano Leonardi v. 40 i. 4 p. 217 - 217
Approximating Min Sum Set Cover
by: Uriel Feige, László Lovász, Prasad Tetali v. 40 i. 4 p. 219 - 234
Sum Coloring of Bipartite Graphs with Bounded Degree
by: Michal Malafiejski, Krzysztof Giaro, Robert Janczewski, Marek Kubale v. 40 i. 4 p. 235 - 244
Primal-Dual Algorithms for Connected Facility Location Problems
by: Chaitanya Swamy, Amit Kumar v. 40 i. 4 p. 245 - 269
The Power of Priority Algorithms for Facility Location and Set Cover
by: Spyros Angelopoulos, Allan Borodin v. 40 i. 4 p. 271 - 291
Admission Control in Networks with Advance Reservations
by: Liane Lewin-Eytan, Joseph Naor, Ariel Orda v. 40 i. 4 p. 293 - 304
Non-Clairvoyant Scheduling for Minimizing Mean Slowdown
by: Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha v. 40 i. 4 p. 305 - 318
On-Line Dial-a-Ride Problems Under a Restricted Information Model
by: Maarten Lipmann, Xiwen Lu, Willem de Paepe, René Sitters, Leen Stougie v. 40 i. 4 p. 319 - 329
An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms
by: Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri v. 41 i. 1 p. 1 - 23
Computing Diameter in the Streaming and Sliding-Window Models
by: Joan Feigenbaum, Sampath Kannan, Jian Zhang v. 41 i. 1 p. 25 - 41
Approximation Algorithms for Quickest Spanning Tree Problems
by: Refael Hassin, Asaf Levin v. 41 i. 1 p. 43 - 52
A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology
by: Guoliang Xue, Wei Xiao v. 41 i. 1 p. 53 - 72
Graph Searching, Elimination Trees, and a Generalization of Bandwidth
by: Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle v. 41 i. 2 p. 73 - 87
New Techniques for Regular Expression Searching
by: Gonzalo Navarro, Mathieu Raffinot v. 41 i. 2 p. 89 - 116
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem
by: Jochen Könemann, Asaf Levin, Amitabh Sinha v. 41 i. 2 p. 117 - 129
A Branch-Checking Algorithm for All-Pairs Shortest Paths
by: Cees Duin v. 41 i. 2 p. 131 - 145

2003

Reporting Red - Blue Intersections between Two Sets of Connected Line Segments
by: Julien Basch, Leonidas J. Guibas, G. D. Ramkumar v. 35 i. 1 p. 1 - 20
Fast Concurrent Access to Parallel Disks
by: Peter Sanders, Sebastian Egner, Jan H. M. Korst v. 35 i. 1 p. 21 - 55
Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast
by: Enrico Nardelli, Guido Proietti, Peter Widmayer v. 35 i. 1 p. 56 - 74
Scanning Multiple Sequences Via Cache Memory
by: Kurt Mehlhorn, Peter Sanders v. 35 i. 1 p. 75 - 93
The Minimum Range Assignment Problem on Linear Radio Networks
by: Andrea E. F. Clementi, Paolo Penna, Afonso Ferreira, Stephane Perennes, Riccardo Silvestri v. 35 i. 2 p. 95 - 110
TSP Heuristics: Domination Analysis and Complexity
by: Abraham P. Punnen, François Margot, Santosh N. Kabadi v. 35 i. 2 p. 111 - 127
Dynamic Programming on the Word RAM
by: David Pisinger v. 35 i. 2 p. 128 - 145
The Data Broadcast Problem with Non-Uniform Transmission Times
by: Claire Kenyon, Nicolas Schabanel v. 35 i. 2 p. 146 - 175
On-Line Edge-Coloring with a Fixed Number of Colors
by: Lene M. Favrholdt, Morten N. Nielsen v. 35 i. 2 p. 176 - 191
Guest Editors' Foreword
by: Hon Wai Leong, Hiroshi Imai v. 35 i. 3 p. 193 - 193
Efficient Parallel Algorithms for Planar st-Graphs
by: Mikhail J. Atallah, Danny Z. Chen, Ovidiu Daescu v. 35 i. 3 p. 194 - 215
An Approximation Algorithm for a Large-Scale Facility Location Problem
by: Hiroyuki Kazuyoshi v. 35 i. 3 p. 216 - 224
Finding a Region with the Minimum Total L1 Distance from Prescribed Terminals
by: Yoshiyuki Takao v. 35 i. 3 p. 225 - 256
A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest
by: Vijaya Chung v. 35 i. 3 p. 257 - 268
A Characterization of Planar Graphs by Pseudo-Line Arrangements
by: Takeshi Hisao v. 35 i. 3 p. 269 - 285
Compressing Two-Dimensional Routing Tables
by: Subhash Suri, Tuomas Sandholm, Priyank Ramesh Warkhede v. 35 i. 4 p. 287 - 300
An Explicit Lower Bound for TSP with Distances One and Two
by: Lars Engebretsen v. 35 i. 4 p. 301 - 318
Detecting Race Conditions in Parallel Programs that Use Semaphores
by: Philip N. Klein, Robert H. B. Netzer, Hsueh-I Lu v. 35 i. 4 p. 321 - 345
Approximate Matching of Run-Length Compressed Strings
by: Veli Mäkinen, Esko Ukkonen, Gonzalo Navarro v. 35 i. 4 p. 347 - 369
An Edit Distance between Quotiented Trees
by: Pascal Ferraro, Christophe Godin v. 36 i. 1 p. 1 - 39
The Solution of Linear Probabilistic Recurrence Relations
by: Louay Bazzi, Sanjoy K. Mitter v. 36 i. 1 p. 41 - 57
Maintenance of a Piercing Set for Intervals with Applications
by: Matthew J. Katz, Frank Nielsen, Michael Segal v. 36 i. 1 p. 59 - 73
A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms
by: Holger Bast, Kurt Mehlhorn, Guido Schäfer v. 36 i. 1 p. 75 - 88
A 3-Party Simultaneous Protocol for SUM-INDEX
by: Xiaoming Sun v. 36 i. 1 p. 89 - 111
An O(n1.5) Deterministic Gossiping Algorithm for Radio Networks
by: Ying Xu 0002 v. 36 i. 1 p. 93 - 96
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms
by: Frank K. H. A. Dehne, Wolfgang Dittrich, David A. Hutchinson v. 36 i. 2 p. 97 - 122
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes
by: Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén v. 36 i. 2 p. 123 - 152
Drawing Trees Symmetrically in Three Dimensions
by: Seok-Hee Hong, Peter Eades v. 36 i. 2 p. 153 - 178
A New Approximation Algorithm for Finding Heavy Planar Subgraphs
by: Gruia Calinescu, Cristina G. Fernandes, Howard J. Karloff, Alexander Zelikovsky v. 36 i. 2 p. 179 - 205
Dynamic TCP Acknowledgment and Other Stories about e/(e-1)
by: Anna R. Karlin, Claire Kenyon, Dana Randall v. 36 i. 3 p. 209 - 224
Competitive On-Line Switching Policies
by: Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor v. 36 i. 3 p. 225 - 247
Static Optimality and Dynamic Search-Optimality in Lists and Trees
by: Avrim Blum, Shuchi Chawla, Adam Kalai v. 36 i. 3 p. 249 - 260
New Bounds for Multidimensional Packing
by: Steven S. Seiden, Rob van Stee v. 36 i. 3 p. 261 - 293
Temporary Tasks Assignment Resolved
by: Amitai Armon, Yossi Azar, Leah Epstein v. 36 i. 3 p. 295 - 314
Multicast Pull Scheduling: When Fairness Is Fine
by: Jeff Edmonds, Kirk Pruhs v. 36 i. 3 p. 315 - 330
Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
by: Satoru Iwata v. 36 i. 4 p. 331 - 341
Escaping a Grid by Edge-Disjoint Paths
by: Wun-Tat Chan, Francis Y. L. Chin, Hing-Fung Ting v. 36 i. 4 p. 343 - 359
Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems
by: Anna Galluccio, Guido Proietti v. 36 i. 4 p. 361 - 374
Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition
by: Hans L. Bodlaender, Udi Rotics v. 36 i. 4 p. 375 - 408
The Buffer Tree: A Technique for Designing Batched External Data Structures
by: Lars Arge v. 37 i. 1 p. 1 - 24
Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems
by: Jens Gramm, Rolf Niedermeier, Peter Rossmanith v. 37 i. 1 p. 25 - 42
Linear Bidirectional On-Line Construction of Affix Trees
by: Moritz G. Maaß v. 37 i. 1 p. 43 - 74
Approximating Node Connectivity Problems via Set Covers
by: Guy Kortsarz, Zeev Nutov v. 37 i. 2 p. 75 - 92
Linear-Time Recognition of Circular-Arc Graphs
by: Ross M. McConnell v. 37 i. 2 p. 93 - 147
Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?
by: Francis Y. L. Chin, Stanley P. Y. Fung v. 37 i. 3 p. 149 - 164
A Distributed Ant Algorithm for Efficiently Patrolling a Network
by: Vladimir Yanovski, Israel A. Wagner, Alfred M. Bruckstein v. 37 i. 3 p. 165 - 186
Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs
by: Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai v. 37 i. 3 p. 187 - 209
Approximation Algorithms for Aligning Points
by: Sergio Cabello, Marc J. van Kreveld v. 37 i. 3 p. 211 - 232
A Linear Time Lower Bound on McCreight and General Updating Algorithms for Suffix Trees
by: Mauricio Ayala-Rincón, Paulo D. Conejo v. 37 i. 3 p. 233 - 241
Semi-On-line Scheduling on Two Parallel Processors with an Upper Bound on the Items
by: Enrico Angelelli, Maria Grazia Speranza, Zsolt Tuza v. 37 i. 4 p. 243 - 262
Reinforcement Learning with Immediate Rewards and Linear Hypotheses
by: Naoki Abe, Alan W. Biermann, Philip M. Long v. 37 i. 4 p. 263 - 293
(Incremental) Priority Algorithms
by: Allan Borodin, Morten N. Nielsen, Charles Rackoff v. 37 i. 4 p. 295 - 326
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
by: Daniel Kobler, Udi Rotics v. 37 i. 4 p. 327 - 346
Shape Algorithmics
by: Remco C. Veltkamp v. 38 i. 1 p. 1 - 4
Polygonal Representations of Digital Sets
by: Ulrich Eckhardt, Helene Reiter v. 38 i. 1 p. 5 - 23
Decomposition of a Three-Dimensional Discrete Object Surface into Discrete Plane Pieces
by: Isabelle Sivignon, Florent Dupont, Jean-Marc Chassery v. 38 i. 1 p. 25 - 43
Comparison of Distance Measures for Planar Curves
by: Helmut Alt, Christian Knauer, Carola Wenk v. 38 i. 1 p. 45 - 58
Combinatorial and Experimental Methods for Approximate Point Pattern Matching
by: Martin Gavrilov, Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian v. 38 i. 1 p. 59 - 90
Free-Form Pose Estimation by Using Twist Representations
by: Bodo Rosenhahn, Christian Perwass, Gerald Sommer v. 38 i. 1 p. 91 - 113
Finding the Consensus Shape for a Protein Family
by: L. Paul Chew, Klara Kedem v. 38 i. 1 p. 115 - 129
New Results on Path Approximation
by: Ovidiu Daescu v. 38 i. 1 p. 131 - 143
Covering with Ellipses
by: Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk v. 38 i. 1 p. 145 - 160
Testing the Quality of Manufactured Disks and Balls
by: Prosenjit Bose, Pat Morin v. 38 i. 1 p. 161 - 177
Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee
by: Tamal K. Dey, Wulue Zhao v. 38 i. 1 p. 179 - 200
A Reflective Symmetry Descriptor for 3D Models
by: Michael M. Kazhdan, Bernard Chazelle, David P. Dobkin, Thomas A. Funkhouser, Szymon Rusinkiewicz v. 38 i. 1 p. 201 - 225
Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes
by: Michela Mortara, Giuseppe Patanè, Michela Spagnuolo, Bianca Falcidieno, Jarek Rossignac v. 38 i. 1 p. 227 - 248
Parallel Computation of the Topology of Level Sets
by: Valerio Pascucci, Kree Cole-McLaughlin v. 38 i. 1 p. 249 - 268
Foreword
by: Tadao Takaoka v. 38 i. 2 p. 269 - 270
Multicolorings of Series-Parallel Graphs
by: Xiao Zhou, Takao Nishizeki v. 38 i. 2 p. 271 - 297
Efficient Algorithms for k-Terminal Cuts on Planar Graphs
by: Danny Z. Chen, Xiaodong Wu v. 38 i. 2 p. 299 - 316
Small Strictly Convex Quadrilateral Meshes of Point Sets
by: David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan v. 38 i. 2 p. 317 - 339
Labeling Points with Weights
by: Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, Takeaki Uno, Alexander Wolff v. 38 i. 2 p. 341 - 362
Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
by: Rudolf Fleischer, Hisashi Koga v. 38 i. 2 p. 363 - 376
Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)
by: Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen v. 38 i. 2 p. 377 - 395
Delay Optimization in Quorum Consensus
by: Xuemin Lin v. 38 i. 2 p. 397 - 413
Guest Editors' Introduction
by: Klaus Jansen, Samir Khuller v. 38 i. 3 p. 415 - 416
Approximation Algorithms for a Capacitated Network Design Problem
by: Refael Hassin, R. Ravi, F. Sibel Salman v. 38 i. 3 p. 417 - 431
An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem
by: Kamal Jain, Vijay V. Vazirani v. 38 i. 3 p. 433 - 439
Improved Approximations for Tour and Tree Covers
by: Jochen Könemann, Goran Konjevod, Ojas Parekh, Amitabh Sinha v. 38 i. 3 p. 441 - 449
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses
by: Venkatesan Guruswami v. 38 i. 3 p. 451 - 469
The Relative Complexity of Approximate Counting Problems
by: Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum v. 38 i. 3 p. 471 - 500
Maximum Dispersion and Geometric Maximum Weight Cliques
by: Sándor P. Fekete, Henk Meijer v. 38 i. 3 p. 501 - 511

2002

A Theoretical and Experimental Study on the Construction of Suffix Arrays in External Memory
by: Andreas Crauser, Paolo Ferragina v. 32 i. 1 p. 1 - 35
On-Line Multi-Threaded Paging
by: Esteban Feuerstein, Alejandro Strejilevich de Loma v. 32 i. 1 p. 36 - 60
Fast Parallel Reordering and Isomorphism Testing of k-Trees
by: John G. Del Greco, Chandra N. Sekharan, R. Sridhar v. 32 i. 1 p. 61 - 72
The Structure and Complexity of Sports Elimination Numbers
by: Dan Gusfield, Charles U. Martel v. 32 i. 1 p. 73 - 86
Algorithms for Coloring Quadtrees
by: David Eppstein, Marshall W. Bern, Brad L. Hutchings v. 32 i. 1 p. 87 - 94
Computing the Cover Array in Linear Time
by: Yin Li, William F. Smyth v. 32 i. 1 p. 95 - 106
Interleaved Prefetching
by: Tracy Kimbrel v. 32 i. 1 p. 107 - 122
Exploring Unknown Environments with Obstacles
by: Susanne Albers, Klaus Kursawe, Sven Schuierer v. 32 i. 1 p. 123 - 143
Improved Algorithms for Constructing Fault-Tolerant Spanners
by: Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid v. 32 i. 1 p. 144 - 156
A Permanent Algorithm with exp[Omega (n1/3/2 ln n )] Expected Speedup for 0-1 Matrices
by: Eric T. Bax, Joel Franklin v. 32 i. 1 p. 157 - 162
Optimal Time-Critical Scheduling via Resource Augmentation
by: Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein v. 32 i. 2 p. 163 - 200
On the Competitive Theory and Practice of Online List Accessing Algorithms
by: Ran Bachrach, Ran El-Yaniv, M. Reinstadtler v. 32 i. 2 p. 201 - 245
Scheduling Independent Multiprocessor Tasks
by: Abdel Krim Amoura, Evripidis Bampis, Claire Kenyon, Yannis Manoussakis v. 32 i. 2 p. 247 - 261
A Divide-and-Conquer Approach to the Minimum k-Way Cut Problem
by: Yoko Kamidoi, Shin'ichi Wakabayashi, Noriyoshi Yoshida v. 32 i. 2 p. 262 - 276
New Algorithms for Disk Scheduling
by: Matthew Andrews, Michael A. Bender, Lisa Zhang v. 32 i. 2 p. 277 - 301
Property Testing in Bounded Degree Graphs
by: Oded Goldreich, Dana Ron v. 32 i. 2 p. 302 - 343
One-by-One Cleaning for Practical Parallel List Ranking
by: Jop F. Sibeyn v. 32 i. 3 p. 345 - 363
Lower Bounds for Dynamic Data Structures on Algebraic RAMs
by: Amir M. Ben-Amram, Zvi Galil v. 32 i. 3 p. 364 - 395
Minimum Congestion Redundant Assignments to Tolerate Random Faults
by: Dimitris Fotakis, Paul G. Spirakis v. 32 i. 3 p. 396 - 422
Embedding Linkages on an Integer Lattice
by: Susan Landau, Neil Immerman v. 32 i. 3 p. 423 - 436
A Functional Approach to External Graph Algorithms
by: James Abello, Adam L. Buchsbaum, Jeffery Westbrook v. 32 i. 3 p. 437 - 458
Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach
by: Edith Cohen, Haim Kaplan v. 32 i. 3 p. 459 - 466
Routing Flow Through a Strongly Connected Graph
by: Thomas Erlebach, Torben Hagerup v. 32 i. 3 p. 467 - 473
Quasi-Upward Planarity
by: Paola Bertolazzi, Giuseppe Di Battista, Walter Didimo v. 32 i. 3 p. 474 - 506
Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks
by: Klaus Jansen, Lorant Porkolab v. 32 i. 3 p. 507 - 520
Improved Algorithms for Uniform Partitions of Points
by: Pankaj K. Agarwal, Binay K. Bhattacharya, Sandeep Sen v. 32 i. 4 p. 521 - 539
An Online Algorithm for the Dynamic Maximal Dense Tree Problem
by: Baruch Awerbuch, Tripurari Singh v. 32 i. 4 p. 540 - 553
Approximations for a Bottleneck Steiner Tree Problem
by: Lusheng Wang, Ding-Zhu Du v. 32 i. 4 p. 554 - 561
Distributed and On-Line Routing on Tori
by: Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, Hsu-Chun Yen v. 32 i. 4 p. 562 - 593
A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems
by: Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller v. 32 i. 4 p. 594 - 610
Algorithmic Aspects of Acyclic Edge Colorings
by: Noga Alon, Ayal Zaks v. 32 i. 4 p. 611 - 614
A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart
by: Uwe Schöning v. 32 i. 4 p. 615 - 623
Randomized Weighted Caching with Two Page Weights
by: Sandy Irani v. 32 i. 4 p. 624 - 640
Delayed Binary Search, or Playing Twenty Questions with a Procrastinator
by: Andris Ambainis, Stephen A. Bloch, David L. Schweizer v. 32 i. 4 p. 641 - 651
Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints
by: Hadas Shachnai, Tami Tamir v. 32 i. 4 p. 651 - 678
Corrigendum: Static Frequency Assignment in Cellular Networks
by: Lata Narayanan, Sunil M. Shende v. 32 i. 4 p. 679 - 679
Foreword
by: Roberto Battiti, Alan A. Bertossi v. 33 i. 1 p. 1 - 2
Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem
by: Laura A. Sanchis v. 33 i. 1 p. 3 - 18
An Experimental Study of Compression Methods for Dynamic Tries
by: Stefan Nilsson, Matti Tikkanen v. 33 i. 1 p. 19 - 33
An Experimental Study of Algorithms for Weighted Completion Time Scheduling
by: Ivan D. Baev, Waleed Meleis, Alexandre E. Eichenberger v. 33 i. 1 p. 34 - 51
A Tutorial for Designing Flexible Geometric Algorithms
by: Vikas Kapoor, Dietmar Kühl, Alexander Wolff v. 33 i. 1 p. 52 - 70
A Neural Algorithm for the Maximum Clique Problem: Analysis, Experiments, and Circuit Implementation
by: Alberto Bertoni, Paola Campadelli, Giuliano Grossi v. 33 i. 1 p. 71 - 88
Experimental Performance of Shared RSA Modulus Generation
by: Rebecca N. Wright, Sara Spalding v. 33 i. 1 p. 89 - 103
Efficient Bulk Operations on Dynamic R-Trees
by: Lars Arge, Klaus Hinrichs, Jan Vahrenhold, Jeffrey Scott Vitter v. 33 i. 1 p. 104 - 128
Fault Identification in System-Level Diagnosis: a Logic-Based Framework and an O(n2sqrt(tau/log n) Algorithm
by: Béchir el Ayeb v. 33 i. 2 p. 129 - 149
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions
by: Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink v. 33 i. 2 p. 150 - 167
Quasi-Fully Dynamic Algorithms for Two-Connectivity and Cycle Equivalence
by: Madhukar R. Korupolu, Vijaya Ramachandran v. 33 i. 2 p. 168 - 182
Efficient Parallel Graph Algorithms for Coarse-Grained Multicomputers and BSP
by: Frank K. H. A. Dehne, Afonso Ferreira, Edson Cáceres, Siang W. Song, Alessandro Roncato v. 33 i. 2 p. 183 - 200
Exact and Approximation Algorithms for Clustering
by: Pankaj K. Agarwal, Cecilia Magdalena Procopiuc v. 33 i. 2 p. 201 - 226
Computing Approximate Shortest Paths on Convex Polytopes
by: Pankaj K. Agarwal, Sariel Har-Peled, Meetesh Karia v. 33 i. 2 p. 227 - 242
Augmenting Trees to Meet Biconnectivity and Diameter Constraints
by: Victor Chepoi, Yann Vaxès v. 33 i. 2 p. 243 - 262
Fast Algorithms for Approximating Distances
by: Sergei Bespamyatnikh, Michael Segal v. 33 i. 2 p. 263 - 269
Guest Editor's Foreword
by: Michael T. Goodrich v. 33 i. 3 p. 271 - 271
Fast, Fair and Frugal Bandwidth Allocation in ATM Networks
by: Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang v. 33 i. 3 p. 272 - 286
Optimal Online Algorithms for an Electronic Commerce Money Distribution System
by: Hiroshi Kawazoe, Tetsuo Shibuya, Takeshi Tokuyama v. 33 i. 3 p. 287 - 299
Exploiting Regularities in Web Traffic Patterns for Cache Replacement
by: Edith Cohen, Haim Kaplan v. 33 i. 3 p. 300 - 334
Extending Greedy Multicast Routing to Delay Sensitive Applications
by: Ashish Goel, Kamesh Munagala v. 33 i. 3 p. 335 - 352
Caching for Web Searching
by: Bala Kalyanasundaram, John Noga, Kirk Pruhs, Gerhard J. Woeginger v. 33 i. 3 p. 353 - 370
On-Line File Caching
by: Neal E. Young v. 33 i. 3 p. 371 - 383
Page Replacement with Multi-Size Pages and Applications to Web Caching
by: Sandy Irani v. 33 i. 3 p. 384 - 409
Some Aperture-Angle Optimization Problems
by: Prosenjit Bose, Ferran Hurtado, Elsa Omaña-Pulido, Jack Snoeyink, Godfried T. Toussaint v. 33 i. 4 p. 411 - 435
Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane
by: Sanguthevar Rajasekaran, Suneeta Ramaswami v. 33 i. 4 p. 436 - 460
Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
by: Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, Rolf Niedermeier v. 33 i. 4 p. 461 - 493
Optimal Solutions for the Temporal Precedence Problem
by: Gerth Stølting Brodal, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas v. 33 i. 4 p. 494 - 510
Competitive Analysis of the LRFU Paging Algorithm
by: Edith Cohen, Haim Kaplan, Uri Zwick v. 33 i. 4 p. 511 - 516
A Near-Linear Area Bound for Drawing Binary Trees
by: Timothy M. Chan v. 34 i. 1 p. 1 - 13
Pinwheel Scheduling: Achievable Densities
by: Peter C. Fishburn, J. C. Lagarias v. 34 i. 1 p. 14 - 38
Splitting a Delaunay Triangulation in Linear Time
by: Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristan, Monique Teillaud v. 34 i. 1 p. 39 - 46
The Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help
by: Thomas Jansen, Ingo Wegener v. 34 i. 1 p. 47 - 66
Testing and Spot-Checking of Data Streams
by: Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan v. 34 i. 1 p. 67 - 80
Realistic Input Models for Geometric Algorithms
by: Mark de Berg, A. Frank van der Stappen, Jules Vleugels, Matthew J. Katz v. 34 i. 1 p. 81 - 97
Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems
by: R. Ravi, David P. Williamson v. 34 i. 1 p. 98 - 107
An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
by: Jean-Daniel Boissonnat, Subir Kumar Ghosh, T. Kavitha, Sylvain Lazard v. 34 i. 2 p. 109 - 156
Further Thoughts on the Syntenic Distance between Genomes
by: Nadia Pisanti, Marie-France Sagot v. 34 i. 2 p. 157 - 180
Fair versus Unrestricted Bin Packing
by: Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen, Leah Epstein v. 34 i. 2 p. 181 - 196
Approximation Algorithms for Access Network Design
by: Matthew Andrews, Lisa Zhang v. 34 i. 2 p. 197 - 215
Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms
by: Olivier Beaumont, Vincent Boudet, Fabrice Rastello, Yves Robert v. 34 i. 3 p. 217 - 239
Max- and Min-Neighborhood Monopolies
by: Kazuhisa Makino, Masafumi Yamashita, Tiko Kameda v. 34 i. 3 p. 240 - 260
Budget Management with Applications
by: Chunhong Chen, Elaheh Bozorgzadeh, Ankur Srivastava, Majid Sarrafzadeh v. 34 i. 3 p. 261 - 275
Communication - Processor Tradeoffs in a Limited Resources PRAM
by: Adnan Agbaria, Yosi Ben-Asher, Ilan Newman v. 34 i. 3 p. 276 - 297
Planar Graph Blocking for External Searching
by: Surender Baswana, Sandeep Sen v. 34 i. 3 p. 298 - 308
Introduction
by: Michele Mosca, Alain Tapp v. 34 i. 4 p. 309 - 313
Secrecy, Computational Loads and Rates in Practical Quantum Cryptography
by: Gerald Gilbert, Michael Hamrick v. 34 i. 4 p. 314 - 339
Security of Practical Time-Reversed EPR Quantum Key Distribution
by: Hitoshi Inamori v. 34 i. 4 p. 340 - 365
Security of Practical BB84 Quantum Key Distribution
by: Hitoshi Inamori v. 34 i. 4 p. 366 - 371
Security of Quantum Key Distribution against All Collective Attacks
by: Eli Biham, Michel Boyer, Gilles Brassard, Jeroen van de Graaf, Tal Mor v. 34 i. 4 p. 372 - 388
Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
by: Nicolas Gisin, Renato Renner, Stefan Wolf v. 34 i. 4 p. 389 - 412
Quantum Algorithms for Weighing Matrices and Quadratic Residues
by: Wim van Dam v. 34 i. 4 p. 413 - 428
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
by: Peter Høyer, Jan Neerbek, Yaoyun Shi v. 34 i. 4 p. 429 - 448
Sharp Quantum versus Classical Query Complexity Separations
by: J. Niel de Beaudrap, Richard Cleve, John Watrous v. 34 i. 4 p. 449 - 461
The Quantum Complexity of Set Membership
by: Jaikumar Radhakrishnan, Pranab Sen, S. Venkatesh v. 34 i. 4 p. 462 - 479
The Quantum Black-Box Complexity of Majority
by: Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek v. 34 i. 4 p. 480 - 501
Remotely Prepared Entanglement: a Quantum Web Page
by: Todd A. Brun v. 34 i. 4 p. 502 - 511
A New Proof for the Existence of Mutually Unbiased Bases
by: Somshubhro Bandyopadhyay, P. Oscar Boykin, Vwani P. Roychowdhury, Farrokh Vatan v. 34 i. 4 p. 512 - 528
The Representation of Numbers in Quantum Mechanics
by: Paul Benioff v. 34 i. 4 p. 529 - 559

2001

Average-Case Analysis of Algorithms - Preface
by: Helmut Prodinger, Wojciech Szpankowski v. 29 i. 1 p. 1 - 2
The Contraction Method for Recursive Algorithms
by: Uwe Rösler, Ludger Rüschendorf v. 29 i. 1 p. 3 - 33
An Algorithmic Approach to Discovering and Proving q-Series Identities
by: George E. Andrews, Arnold Knopfmacher v. 29 i. 1 p. 34 - 43
Transitional Behaviors of the Average Cost of Quicksort with Median-of-(2t+1)
by: Hua-Huai Chern, Hsien-Kuei Hwang v. 29 i. 1 p. 44 - 69
Bandwidth Packing
by: Edward G. Coffman Jr., Alexander L. Stolyar v. 29 i. 1 p. 70 - 88
An Analytic Approach to the Height of Binary Search Trees
by: Michael Drmota v. 29 i. 1 p. 89 - 119
A Unified Presentation of Some Urn Models
by: Michael Drmota, Danièle Gardy, Bernhard Gittenberger v. 29 i. 1 p. 120 - 147
Near-Optimal Bounded-Degree Spanning Trees
by: Jennie C. Hansen, Eric Schmutz v. 29 i. 1 p. 148 - 180
Partial Match Queries in Relaxed Multidimensional Search Trees
by: Conrado Martinez, Alois Panholzer, Helmut Prodinger �