Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings (Lecture Notes in Computer Science, 7276)

This book constitutes the refereed proceedings of the 11th International Symposium on Experimental Algorithms, SEA 2012, held Bordeaux, France, in June 2012. The 31 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 64 submissions and present current research in the area of design, analysis, and experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications. Front Matter....Pages - Automatic Decomposition and Branch-and-Price—A Status Report....Pages 1-8 Continuous Local Strategies for Robotic Formation Problems....Pages 9-17 Engineering Graph Partitioning Algorithms....Pages 18-26 Space Efficient Modifications to Structator— A Fast Index-Based Search Tool for RNA Sequence-Structure Patterns....Pages 27-38 Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs....Pages 39-50 How to Attack the NP-Complete Dag Realization Problem in Practice....Pages 51-62 New Results about Multi-band Uncertainty in Robust Optimization....Pages 63-74 Compact Relaxations for Polynomial Programming Problems....Pages 75-86 Relaxations of Multilinear Convex Envelopes: Dual Is Better Than Primal....Pages 87-98 On Computing the Diameter of Real-World Directed (Weighted) Graphs....Pages 99-110 Reoptimizing the Strengthened Metric TSP on Multiple Edge Weight Modifications....Pages 111-122 Engineering a New Loop-Free Shortest Paths Routing Algorithm....Pages 123-134 Fully Dynamic Maintenance of Arc-Flags in Road Networks....Pages 135-147 A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs....Pages 148-159 Branch Mispredictions Don’t Affect Mergesort....Pages 160-171 A Multiple Sliding Windows Approach to Speed Up String Matching Algorithms....Pages 172-183 Algorithms for Subnetwork Mining in Heterogeneous Networks....Pages 184-194 Computing Strong Articulation Points and Strong Bridges in Large Scale Graphs....Pages 195-207 Adaptive Distributed b-Matching in Overlays with Preferences....Pages 208-223 Dynamizing Succinct Tree Representations....Pages 224-235 A Label Correcting Algorithm for the Shortest Path Problem on a Multi-modal Route Network....Pages 236-247 Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data....Pages 248-259 Candidate Sets for Alternative Routes in Road Networks....Pages 260-270 Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation....Pages 271-282 An Evaluation of Community Detection Algorithms on Large-Scale Email Traffic....Pages 283-294 Fast, Small, Simple Rank/Select on Bitmaps....Pages 295-306 Space-Efficient Top-k Document Retrieval....Pages 307-319 Engineering Efficient Paging Algorithms....Pages 320-331 Feasibility Pump Heuristics for Column Generation Approaches....Pages 332-343 Exact Graph Search Algorithms for Generalized Traveling Salesman Path Problems....Pages 344-355 Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach....Pages 356-368 Advanced Coarsening Schemes for Graph Partitioning....Pages 369-380 A Heuristic for Non-convex Variance-Based Clustering Criteria....Pages 381-392 A Decomposition Approach for Solving Critical Clique Detection Problems....Pages 393-404 Back Matter....Pages -