Algorithms and Data Structures 10th International Workshop, WADS 2007, Halifax, Canada, August 15-17, 2007. Proceedings /

• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Άλλοι συγγραφείς: Dehne, Frank (Επιμελητής έκδοσης), Sack, Jörg-Rüdiger (Επιμελητής έκδοσης), Zeh, Norbert (Επιμελητής έκδοσης)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2007.
• Σειρά: Lecture Notes in Computer Science, 4619
• Θέματα: Computer science.; Computer programming.; Data structures (Computer science).; Algorithms.; Numerical analysis.; Computer science > Mathematics.; Computer graphics.; Computer Science.; Programming Techniques.; Algorithm Analysis and Problem Complexity.; Data Structures.; Discrete Mathematics in Computer Science.; Computer Graphics.; Numeric Computing.

The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- di...

Πίνακας περιεχομένων:

• Session 1
• Finding Small Holes
• Session 2A
• Approximate Range Searching: The Absolute Model
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• Session 2B
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• Approximating the Maximum Sharing Problem
• The Stackelberg Minimum Spanning Tree Game
• Session 3A
• Edges and Switches, Tunnels and Bridges
• How to Draw a Clustered Tree
• Drawing Colored Graphs on Colored Points
• Session 3B
• Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
• Priority Queues Resilient to Memory Faults
• Simple and Space-Efficient Minimal Perfect Hash Functions
• Session 4A
• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• Optimization for First Order Delaunay Triangulations
• Session 4B
• Constant Factor Approximations for the Hotlink Assignment Problem
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A Stab at Approximating Minimum Subadditive Join
• Session 5
• Algorithmic Challenges for Systems-Level Correlational Analysis: A Tale of Two Datasets
• Session 6A
• Flooding Countries and Destroying Dams
• I/O-Efficient Flow Modeling on Fat Terrains
• Computing the Visibility Map of Fat Objects
• Session 6B
• Independent Sets in Bounded-Degree Hypergraphs
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Computing a Minimum-Depth Planar Graph Embedding in O(n 4) Time
• Session 7A
• On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
• Spanners for Geometric Intersection Graphs
• On Generalized Diamond Spanners
• Session 7B
• The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces
• On the Robustness of Graham’s Algorithm for Online Scheduling
• Improved Results for a Memory Allocation Problem
• Session 8A
• Computational and Structural Advantages of Circular Boundary Representation
• Alpha-Beta Witness Complexes
• Cauchy’s Theorem and Edge Lengths of Convex Polyhedra
• Session 8B
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Improved Algorithms for the Feedback Vertex Set Problems
• Kernelization Algorithms for d-Hitting Set Problems
• Session 9A
• Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points
• Maximizing Maximal Angles for Plane Straight-Line Graphs
• Cuttings for Disks and Axis-Aligned Rectangles
• Session 9B
• Kernelization and Complexity Results for Connectivity Augmentation Problems
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Branch and Recharge: Exact Algorithms for Generalized Domination
• Session 10A
• On Computing the Centroid of the Vertices of an Arrangement and Related Problems
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• Session 10B
• Faster Approximation of Distances in Graphs
• Approximate Shortest Paths Guided by a Small Index
• Session 11A
• Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model
• Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• On Euclidean Vehicle Routing with Allocation
• Session 11B
• Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets
• Range Non-overlapping Indexing and Successive List Indexing
• Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton’s Identities and Invertible Bloom Filters
• Dynamic TCP Acknowledgment with Sliding Window.