Experimental and Efficient Algorithms: 4th International Workshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005. Proceedings

Front Matter....Pages -
 Tα Π αι δí α Π α í ζε ι The Interaction Between Algorithms and Game Theory....Pages 1-3
Using an Adaptive Memory Strategy to Improve a Multistart Heuristic for Sequencing by Hybridization....Pages 4-15
High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology....Pages 16-21
The “Real” Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting....Pages 22-31
Implementing Minimum Cycle Basis Algorithms....Pages 32-43
Rounding to an Integral Program....Pages 44-54
Rectangle Covers Revisited Computationally....Pages 55-66
Don’t Compare Averages....Pages 67-76
Experimental Results for Stackelberg Scheduling Strategies....Pages 77-88
An Improved Branch-and-Bound Algorithm for the Test Cover Problem....Pages 89-100
Degree-Based Treewidth Lower Bounds....Pages 101-112
Inferring AS Relationships: Dead End or Lively Beginning?....Pages 113-125
Acceleration of Shortest Path and Constrained Shortest Path Computation....Pages 126-138
A General Buffer Scheme for the Windows Scheduling Problem....Pages 139-151
Implementation of Approximation Algorithms for the Multicast Congestion Problem....Pages 152-164
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes....Pages 165-176
From Static Code Distribution to More Shrinkage for the Multiterminal Cut....Pages 177-188
Partitioning Graphs to Speed Up Dijkstra’s Algorithm....Pages 189-202
Efficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games....Pages 203-215
New Upper Bound Heuristics for Treewidth....Pages 216-227
Accelerating Vickrey Payment Computation in Combinatorial Auctions for an Airline Alliance....Pages 228-239
Algorithm Engineering for Optimal Graph Bipartization....Pages 240-252
Empirical Analysis of the Connectivity Threshold of Mobile Agents on the Grid....Pages 253-264
Multiple-Winners Randomized Tournaments with Consensus for Optimization Problems in Generic Metric Spaces....Pages 265-276
On Symbolic Scheduling Independent Tasks with Restricted Execution Times....Pages 277-289
A Simple Randomized k -Local Election Algorithm for Local Computations....Pages 290-301
Generating and Radiocoloring Families of Perfect Graphs....Pages 302-314
Efficient Implementation of Rank and Select Functions for Succinct Representation....Pages 315-327
Comparative Experiments with GRASP and Constraint Programming for the Oil Well Drilling Problem....Pages 328-340
A Framework for Probabilistic Numerical Evaluation of Sensor Networks: A Case Study of a Localization Protocol....Pages 341-353
A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables....Pages 354-366
GRASP with Path-Relinking for the Weighted Maximum Satisfiability Problem....Pages 367-379
New Bit-Parallel Indel-Distance Algorithm....Pages 380-390
Dynamic Application Placement Under Service and Memory Constraints....Pages 391-402
Integrating Coordinated Checkpointing and Recovery Mechanisms into DSM Synchronization Barriers....Pages 403-414
Synchronization Fault Cryptanalysis for Breaking A5/1....Pages 415-427
An Efficient Algorithm for δ -Approximate Matching with α -Bounded Gaps in Musical Sequences....Pages 428-439
The Necessity of Timekeeping in Adversarial Queueing....Pages 440-451
BDDs in a Branch and Cut Framework....Pages 452-463
Parallel Smith-Waterman Algorithm for Local DNA Comparison in a Cluster of Workstations....Pages 464-475
Fast Algorithms for Weighted Bipartite Matching....Pages 476-487
A Practical Minimal Perfect Hashing Method....Pages 488-500
Efficient and Experimental Meta-heuristics for MAX-SAT Problems....Pages 501-512
Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs....Pages 513-523
Local Clustering of Large Graphs by Approximate Fiedler Vectors....Pages 524-533
Almost FPRAS for Lattice Models of Protein Folding....Pages 534-544
Vertex Cover Approximations: Experiments and Observations....Pages 545-557
GRASP with Path-Relinking for the Maximum Diversity Problem....Pages 558-569
How to Splay for loglog N -Competitiveness....Pages 570-579
Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms....Pages 580-592
Optimal Competitive Online Ray Search with an Error-Prone Robot....Pages 593-596
An Empirical Study for Inversions-Sensitive Sorting Algorithms....Pages 597-601
Approximation Algorithm for Chromatic Index and Edge-Coloring of Multigraphs....Pages 602-605
Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study....Pages 606-609
Selecting the Roots of a Small System of Polynomial Equations by Tolerance Based Matching....Pages 610-613
Developing Novel Statistical Bandwidths for Communication Networks with Incomplete Information....Pages 614-617
Dynamic Quality of Service Support in Virtual Private Networks....Pages 618-621
Back Matter....Pages -