Algorithm Theory — SWAT 2002: 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002 Proceedings

An Efficient Quasidictionary....Pages 1-18
Combining Pattern Discovery and Probabilistic Modeling in Data Mining....Pages 19-19
Time and Space Efficient Multi-method Dispatching....Pages 20-29
Linear Time Approximation Schemes for Vehicle Scheduling....Pages 30-39
Minimizing Makespan for the Lazy Bureaucrat Problem....Pages 40-50
A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times....Pages 51-59
Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains....Pages 60-68
Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D....Pages 69-79
Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains....Pages 80-89
Exact Algorithms and Approximation Schemes for Base Station Placement Problems....Pages 90-99
A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels....Pages 100-109
Optimal Algorithm for a Special Point-Labeling Problem....Pages 110-120
Random Arc Allocation and Applications....Pages 121-130
On Neighbors in Geometric Permutations....Pages 131-139
Powers of Geometric Intersection Graphs and Dispersion Algorithms....Pages 140-149
Efficient Data Reduction for Dominating Set : A Linear Problem Kernel for the Planar Case....Pages 150-159
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous....Pages 160-169
Approximation Hardness of the Steiner Tree Problem on Graphs....Pages 170-179
The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus....Pages 180-189
The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms....Pages 190-199
A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid....Pages 200-209
Approximation Algorithms for Edge-Dilation k -Center Problems....Pages 210-219
Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm....Pages 220-229
Improved Algorithms for the Random Cluster Graph Model....Pages 230-239
Δ-List Vertex Coloring in Linear Time....Pages 240-248
Robot Localization without Depth Perception....Pages 249-259
Online Parallel Heuristics and Robot Searching under the Competitive Framework....Pages 260-269
Analysis of Heuristics for the Freeze-Tag Problem....Pages 270-279
Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems....Pages 280-287
All-Norm Approximation Algorithms....Pages 288-297
Approximability of Dense Instances of Nearest Codeword Problem....Pages 298-307
Call Control with k Rejections....Pages 308-317
On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem....Pages 318-327
Packet Bundling....Pages 328-337
Algorithms for the Multi-constrained Routing Problem....Pages 338-347
Computing the Threshold for q -Gram Filters....Pages 348-357
On the Generality of Phylogenies from Incomplete Directed Characters....Pages 358-367
Sorting with a Forklift....Pages 368-377
Tree Decompositions with Small Cost....Pages 378-387
Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition....Pages 388-397
Performance Tuning an Algorithm for Compressing Relational Tables....Pages 398-407
A Randomized In-Place Algorithm for Positioning the k th Element in a Multiset....Pages 408-417
Paging on a RAM with Limited Resources....Pages 418-427
An Optimal Algorithm for Finding NCA on Pure Pointer Machines....Pages 428-438
Amortized Complexity of Bulk Updates in AVL-Trees....Pages 439-448