Algorithm Engineering and Experiments: 4th International Workshop, ALENEX 2002 San Francisco, CA, USA, January 4–5, 2002 Revised Papers

Marcus Poggi de Aragão, Renato F. Werneck (auth.), David M. Mount, Clifford Stein (eds.)3540439773, 9783540439776

This book constitutes the thoroughly refereed post-proceedings of the 4th International Workshop on Algorithm Engineering and Experiments, ALENEX 2002, held in San Francisico, CA, USA in January 2002.
The 15 revised full papers presented were carefully reviewed and selected from 34 submissions. Among the topics addressed are hewistics for algorithms, combinatorial optimization, searching, graph computation, network optimization, scheduling, computational geometry, sorting, and clustering algorithms.

---

Table of contents :
On the Implementation of MST-Based Heuristics for the Steiner Problem in Graphs….Pages 1-15
A Time-Sensitive System for Black-Box Combinatorial Optimization….Pages 16-28
A Compressed Breadth-First Search for Satisfiability….Pages 29-42
Using Multi-level Graphs for Timetable Information in Railway Systems….Pages 43-59
Evaluating the Local Ratio Algorithm for Dynamic Storage Allocation….Pages 60-70
An Experimental Study of Prefetching and Caching Algorithms for the World Wide Web….Pages 71-85
The Treewidth of Java Programs….Pages 86-97
Partitioning Planar Graphs with Costs and Weights….Pages 98-110
Maintaining Dynamic Minimum Spanning Trees: An Experimental Study….Pages 111-125
Experimental Evaluation of a New Shortest Path Algorithm….Pages 126-142
Getting More from Out-of-Core Columnsort….Pages 143-154
Topological Sweep in Degenerate Cases….Pages 155-165
Acceleration of K-Means and Related Clustering Algorithms….Pages 166-177
STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects….Pages 178-193
An Improvement on Tree Selection Sort….Pages 194-205