Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005. Proceedings

Front Matter....Pages -
Towards a Theory of Algorithms....Pages 1-1
k-Restricted Rotation with an Application to Search Tree Rebalancing....Pages 2-13
Heap Building Bounds....Pages 14-23
The Multi-radius Cover Problem....Pages 24-35
Parameterized Complexity of Generalized Vertex Cover Problems....Pages 36-48
The Complexity of Implicit and Space Efficient Priority Queues....Pages 49-60
Analysis of a Class of Tries with Adaptive Multi-digit Branching....Pages 61-72
Balanced Aspect Ratio Trees Revisited....Pages 73-85
Improved Combinatorial Group Testing for Real-World Problem Sizes....Pages 86-98
Parameterized Counting Algorithms for General Graph Covering Problems....Pages 99-109
Approximating the Online Set Multicover Problems via Randomized Winnowing....Pages 110-121
Max-stretch Reduction for Tree Spanners....Pages 122-133
Succinct Representation of Triangulations with a Boundary....Pages 134-145
Line-Segment Intersection Made In-Place....Pages 146-157
Improved Fixed-Parameter Algorithms for Two Feedback Set Problems....Pages 158-168
Communication-Aware Processor Allocation for Supercomputers....Pages 169-181
Dynamic Hotlinks....Pages 182-194
The Minimum-Area Spanning Tree Problem....Pages 195-204
Hinged Dissection of Polypolyhedra....Pages 205-217
Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms....Pages 218-232
Linear Time Algorithms for Generalized Edge Dominating Set Problems....Pages 233-243
On Geometric Dilation and Halving Chords....Pages 244-255
Orthogonal Subdivisions with Low Stabbing Numbers....Pages 256-268
Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes....Pages 269-281
Approximation Algorithms for Forests Augmentation Ensuring Two Disjoint Paths of Bounded Length....Pages 282-293
A Dynamic Implicit Adjacency Labelling Scheme for Line Graphs....Pages 294-305
The On-line Asymmetric Traveling Salesman Problem....Pages 306-317
All-Pairs Shortest Paths with Real Weights in O ( n 3 /log n ) Time....Pages 318-324
 k -Link Shortest Paths in Weighted Subdivisions....Pages 325-337
Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices....Pages 338-349
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems....Pages 350-359
On the Vehicle Routing Problem....Pages 360-371
The Structure of Optimal Prefix-Free Codes in Restricted Languages: The Uniform Probability Case....Pages 372-384
Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms....Pages 385-395
Derandomization of Dimensionality Reduction and SDP Based Algorithms....Pages 396-408
Subquadratic Algorithms for 3SUM....Pages 409-421
Near-Optimal Pricing in Near-Linear Time....Pages 422-431
Improved Approximation Bounds for Planar Point Pattern Matching....Pages 432-443
Back Matter....Pages -