Torben Hagerup, Rajeev Raman (auth.), Martti Penttonen, Erik Meineche Schmidt (eds.)
The 43 revised full papers presented together with two invited contributions were carefully reviewed and selected from 103 submissions. The papers are organized in topical sections on scheduling, computational geometry, graph algorithms, robotics, approximation algorithms, data communication, computational biology, and data storage and manipulation.
Table of contents :
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
Reviews
There are no reviews yet.