Algorithm theory - SWAT 2002(算法理论－SWAT2002/会议录)

This book constitutes the refereed proceedings of the 8th Scandinavian Workshop on Algorithm Theory, SWAT 2002, held in Turku, Finland, in July 2002.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.

在线阅读本书

This book constitutes the refereed proceedings of the 8th Scandinavian Workshop on Algorithm Theory, SWAT 2002, held in Turku, Finland, in July 2002.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.

Invited Speakers
An Efficient Quasidictionary
Combining Pattern Discovery and Probabilistic Modeling in Data Mining
Scheduling
Time and Space Efficient Multi-method Dispatching
Linear Time Approximation Schemes for Vehicle Scheduling
Minimizing Makespan for the Lazy Bureaucrat Problem
A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times
Computational Geometry
Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains
Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D
Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains
Exact Algorithms and Approximation Schemes for Base Station Placement Problems
A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels
Optimal Algorithm for a Special Point-Labeling Problem
Random Arc Allocation and Applications
On Neighbors in Geometric Permutations
Graph Algorithms
Powers of Geometric Intersection Graphs and Dispersion Algorithms
Efficient Data Reduction for DOMINATING SET: A Linear Problem Kernel for the Planar Case
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous
Approximation Hardness of the Steiner Tree Problem on Graphs
The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus
The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms
A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid
Approximation Algorithms for Edge-Dilation k-Center Problems
Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm
……
Robotics
Approximation Algorithms
Data Communication
Computational Biology
Data Storage and Manipulation
Author Index