This volume constitutes the refereed proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010, held on Ischia Island, Naples, Italy, in May 2010. The 40 revised full papers presented together with two invited papers were carefully reviewed and selected from 73 submissions. The topics covered include algorithm engineering, algorithmic libraries, algorithmic mechanism design, analysis of algorithms, algorithms for memory hierarchies, approximation techniques, bioinformatics, branch and bound algorithms, combinatorial and irregular problems, combinatorial structures and graphs, communication networks, complex networks, computational geometry, computational learning theory, computational optimization, computer systems, cryptography and security, data streams, data structures, distributed and parallel algorithms, evaluation of algorithms for realistic environments, experimental techniques and statistics, graph drawing, heuristics for combinatorial optimization
Author(s): Umberto Ferraro-Petrillo, Irene Finocchi, Giuseppe F. Italiano (auth.), Paola Festa (eds.)
Series: Lecture Notes in Computer Science 6049 : Programming and Software Engineering
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 514
Tags: Algorithm Analysis and Problem Complexity; Artificial Intelligence (incl. Robotics); Information Systems Applications (incl.Internet); Computer Communication Networks; Information Storage and Retrieval; Database Management
Front Matter....Pages -
Experimental Study of Resilient Algorithms and Data Structures....Pages 1-12
Computational Challenges with Cliques, Quasi-cliques and Clique Partitions in Graphs....Pages 13-22
Alternative Routes in Road Networks....Pages 23-34
Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks....Pages 35-46
Space-Efficient SHARC-Routing....Pages 47-58
A New Fully Dynamic Algorithm for Distributed Shortest Paths and Its Experimental Evaluation....Pages 59-70
Contraction of Timetable Networks with Realistic Transfers....Pages 71-82
Distributed Time-Dependent Contraction Hierarchies....Pages 83-93
Practical Compressed Suffix Trees....Pages 94-105
Maximum Cliques in Protein Structure Comparison....Pages 106-117
Exact Bipartite Crossing Minimization under Tree Constraints....Pages 118-128
Bit-Parallel Search Algorithms for Long Patterns....Pages 129-140
Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments....Pages 141-153
Experimental Evaluation of Approximation and Heuristic Algorithms for Sorting Railway Cars....Pages 154-165
Time-Dependent Contraction Hierarchies and Approximation....Pages 166-177
A New Combinational Logic Minimization Technique with Applications to Cryptology....Pages 178-189
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements....Pages 190-201
The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm....Pages 202-213
An Approximate ε -Constraint Method for the Multi-objective Undirected Capacitated Arc Routing Problem....Pages 214-225
A Branch-and-Price Algorithm for Multi-mode Resource Leveling....Pages 226-238
Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs....Pages 239-252
Using Bound Sets in Multiobjective Optimization: Application to the Biobjective Binary Knapsack Problem....Pages 253-265
Improving Cutting Plane Generation with 0-1 Inequalities by Bi-criteria Separation....Pages 266-275
New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery....Pages 276-287
A Metaheuristic for a Two Echelon Location-Routing Problem....Pages 288-301
New Fast Heuristics for the 2D Strip Packing Problem with Guillotine Constraint....Pages 302-313
An Experimental Comparison of Different Heuristics for the Master Bay Plan Problem....Pages 314-325
An Analysis of Heuristics for Vertex Colouring....Pages 326-337
Automatic Tuning of GRASP with Path-Relinking Heuristics with a Biased Random-Key Genetic Algorithm....Pages 338-349
Experiments with a Feasibility Pump Approach for Nonconvex MINLPs....Pages 350-360
Paging Multiple Users in Cellular Network: Yellow Page and Conference Call Problems....Pages 361-372
Realtime Classification for Encrypted Traffic....Pages 373-385
Data Propagation with Guaranteed Delivery for Mobile Networks....Pages 386-397
Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries....Pages 398-410
Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure....Pages 411-423
Policy-Based Benchmarking of Weak Heaps and Their Relatives,....Pages 424-435
Modularity-Driven Clustering of Dynamic Graphs....Pages 436-448
Gateway Decompositions for Constrained Reachability Problems....Pages 449-461
Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere....Pages 462-473
Fault Recovery in Wireless Networks: The Geometric Recolouring Approach....Pages 474-485
Geometric Minimum Spanning Trees with GeoFilterKruskal ....Pages 486-500
Practical Nearest Neighbor Search in the Plane....Pages 501-512
Back Matter....Pages -
