Front matter
163-180
An Efficient Quasidictionary
Torben Hagerup and Rajeev Raman
57-60
Combining Pattern Discovery and Probabilistic Modeling in Data Mining
Heikki Mannila
39-54
Time and Space Efficient Multi-method Dispatching
Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz and Theis Rauhe
30-39
Linear Time Approximation Schemes for Vehicle Scheduling
John E. Augustine and Steven S. Seiden
277-292
Minimizing Makespan for the Lazy Bureaucrat Problem
Clint Hepner and Cliff Stein
249-262
A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times
Monaldo Mastrolilli
153-225
Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains
Stephan Eidenbenz
49-70
Simplex Range Searching and
k
Nearest Neighbors of a Line Segment in 2D
Partha P. Goswami, Sandip Das and Subhas C. Nandy
319-333
Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains
Christos Levcopoulos, Andrzej Lingas and Joseph S. B. Mitchell
15-27
Exact Algorithms and Approximation Schemes for Base Station Placement Problems
Nissan Lev-Tov and David Peleg
149-161
A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels
Zhongping Qin and Binhai Zhu
153-156
Optimal Algorithm for a Special Point-Labeling Problem
Sasanka Roy, Partha P. Goswami, Sandip Das and Subhas C. Nandy
121-130
Random Arc Allocation and Applications
Peter Sanders and Berthold Vöcking
131-139
On Neighbors in Geometric Permutations
Micha Sharir and Shakhar Smorodinsky
293-304
Powers of Geometric Intersection Graphs and Dispersion Algorithms
Geir Agnarsson, Peter Damaschke and Magnús M. Halldórsson
567-588
Efficient Data Reduction for Dominating Set
: A Linear Problem Kernel for the Planar Case
Jochen Alber, Michael R. Fellows and Rolf Niedermeier
3-6
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous
Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl and Gerhard J. Woeginger
95-99
Approximation Hardness of the Steiner Tree Problem on Graphs
Miroslav Chlebík and Janka Chlebíková
7-19
The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus
J. Ellis, H. Fan and M. Fellows
347-348
The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms
Harold N. Gabow and Seth Pettie
200-209
A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid
Alexander Golynski and Joseph D. Horton
187-207
Approximation Algorithms for Edge-Dilation k-Center Problems
Jochen Könemann, Yanjun Li, Ojas Parekh and Amitabh Sinha
1-13
Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm
Sarnath Ramnath
230-239
Improved Algorithms for the Random Cluster Graph Model
Ron Shamir and Dekel Tsur
301-390
Δ-List Vertex Coloring in Linear Time
San Skulrattanakulchai
177-194
Robot Localization without Depth Perception
Erik D. Demaine, Alejandro López-Ortiz and J. Ian Munro
61-63
Online Parallel Heuristics and Robot Searching under the Competitive Framework
Alejandro López-Ortiz and Sven Schuierer
113-130
Analysis of Heuristics for the Freeze-Tag Problem
Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender and Joseph S. B. Mitchell
275-299
Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems
Esther M. Arkin, Refael Hassin, Shlomi Rubinstein and Maxim Sviridenko
71-88
All-Norm Approximation Algorithms
Yossi Azar, Leah Epstein, Yossi Richter and Gerhard J. Woeginger
298-307
Approximability of Dense Instances of Nearest Codeword
Problem
1Cristina Bazgan, W. Fernandez de la Vega and Marek Karpinski
33-47
Call Control with
k
Rejections
R. Sai Anand, Thomas Erlebach, Alexander Hall and Stamatis Stefanakos
589-643
On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem
Guy Even, Guy Kortsarz and Wolfgang Slany
1-38
Packet Bundling
Jens S. Frederiksen and Kim S. Larsen
97-112
Algorithms for the Multi-constrained Routing Problem
Anuj Puri and Stavros Tripakis
111-124
Computing the Threshold for
q
-Gram Filters
Juha Kärkkäinen
195-214
On the Generality of Phylogenies from Incomplete Directed Characters
Itsik Pe’er, Ron Shamir and Roded Sharan
141-161
Sorting with a Forklift
M. H. Albert and M. D. Atkinson
215-236
Tree Decompositions with Small Cost
Hans L. Bodlaender and Fedor V. Fomin
213-222
Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition
Hans L. Bodlaender and Udi Rotics
185-194
Performance Tuning an Algorithm for Compressing Relational Tables
Jyrki Katajainen and Jeppe Nejsum Madsen
81-87
A Randomized In-Place Algorithm for Positioning the
k
th Element in a Multiset
Jyrki Katajainen and Tomi A. Pasanen
418-427
Paging on a RAM with Limited Resources
Tony W. Lai
428-438
An Optimal Algorithm for Finding NCA on Pure Pointer Machines
A. Dal Palú, E. Pontelli and D. Ranjan
89-108
Amortized Complexity of Bulk Updates in AVL-Trees
Eljas Soisalon-Soininen and Peter Widmayer
Back matter