Experimental Algorithms: 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006. Proceedings

Sotiris Nikoletseas (auth.), Carme Àlvarez, María Serna (eds.)3540345973, 9783540345978

This book constitutes the refereed proceedings of the 5th International Workshop on Experimental and Efficient Algorithms, WEA 2006, held in Cala Galdana, Menorca, Spain in May 2006.

The 26 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 92 submissions. The book is devoted to the design, analysis, implementation, experimental evaluation, and engineering of efficient algorithms. Among the application areas addressed are most fields applying advanced algorithmic techniques, such as combinatorial optimization, approximation, graph theory, discrete mathematics, scheduling, searching, sorting, string matching, coding, networking, etc.

---

Table of contents :
Front Matter….Pages –
Algorithms for Wireless Sensor Networks: Design, Analysis and Experimental Evaluation….Pages 1-12
Numerical Estimation of the Impact of Interferences on the Localization Problem in Sensor Networks….Pages 13-23
An Efficient Heuristic for the Ring Star Problem….Pages 24-35
An Incremental Model for Combinatorial Maximization Problems….Pages 36-48
Workload Balancing in Multi-stage Production Processes….Pages 49-60
Fault Cryptanalysis and the Shrinking Generator….Pages 61-72
Some Advances in the Theory of Voting Systems Based on Experimental Algorithms….Pages 73-84
Practical Construction of k -Nearest Neighbor Graphs in Metric Spaces….Pages 85-97
Fast and Simple Approximation of the Diameter and Radius of a Graph….Pages 98-108
Lists on Lists: A Framework for Self-organizing Lists in Environments with Locality of Reference….Pages 109-120
Lists Revisited: Cache Conscious STL Lists….Pages 121-133
Engineering the LOUDS Succinct Tree Representation….Pages 134-145
Faster Adaptive Set Intersections for Text Searching….Pages 146-157
Compressed Dictionaries: Space Measures, Data Sets, and Experiments….Pages 158-169
Efficient Bit-Parallel Algorithms for ( δ , α )-Matching….Pages 170-181
Tiny Experiments for Algorithms and Life….Pages 182-182
Evaluation of Online Strategies for Reordering Buffers….Pages 183-194
Scheduling Unrelated Parallel Machines Computational Results….Pages 195-206
Implementation of Approximation Algorithms for the Max-Min Resource Sharing Problem….Pages 207-218
Column Generation Based Heuristic for a Helicopter Routing Problem….Pages 219-230
Kernels for the Vertex Cover Problem on the Preferred Attachment Model….Pages 231-240
Practical Partitioning-Based Methods for the Steiner Problem….Pages 241-252
Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems….Pages 253-264
A Maximum Profit Coverage Algorithm with Application to Small Molecules Cluster Identification….Pages 265-276
Algorithmic Challenges in Web Search Engines….Pages 277-278
On the Least Cost for Proximity Searching in Metric Spaces….Pages 279-290
Updating Directed Minimum Cost Spanning Trees….Pages 291-302
Experiments on Exact Crossing Minimization Using Column Generation….Pages 303-315
Goal Directed Shortest Path Queries Using P recomputed C luster D istances….Pages 316-327
Back Matter….Pages –