Algorithm Engineering : 3rd International Workshop, WAE'99, London, UK, July 19-21, 1999, Proceedings

by International Workshop on Algorithm Engineering 1999 (London, England); Vitter, Jeffrey Scott; Zaroliagis, Christos D.

• ISBN13: 9783540664277
• ISBN10: 3540664270
• Format: Paperback
• Copyright: 1999-09-01
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the Third International Workshop on Algorithm Engineering, WAE'99, held in London, UK in July 1999.The 24 revised full papers presented were carefully reviewed and selected from a total of 46 submissions. The papers present original research results in all aspects of algorithm engineering including implementation, experimental testing, fine-tuning of discrete algorithms, development of repositories of software, methodological issues such as standards for empirical research on algorithms and data structures, and issues in the process of converting user requirements into efficient algorithmic solutions and implementations.

Table of Contents

Invited Lectures
Selecting Problems for Algorithm Evaluation	1	(11)
Andrew V. Goldberg
BSP Algorithms -- ``Write Once, Run Anywhere''	12	(2)
Bill McColl
Ten years of LEDA: Some Thoughts	14	(1)
Kurl Mehlhorn
Contributed Papers
Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison	15	(15)
Victor M. Jimenez
Andres Marzal
Efficient Implementation of Lazy Suffix Trees	30	(13)
Robert Giegerich
Stefan Kurtz
Jens Stoye
Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism (Extended Abstract)	43	(17)
Shlomit Dascal
Uzi Vishkin
Finding Minimum Congestion Spanning Trees	60	(12)
Renato Fonseca F. Werneck
Joao Carlos Setubal
Arlindo F. da Conceicao
Evaluation of an Algorithm for the Transversal Hypergraph Problem	72	(13)
Dimitris J. Kavvadias
Elias C. Stavropoulos
Construction Heuristics and Domination of Analysis for the Asymmetric TSP	85	(10)
Fred Glover
Gregory Gutin
Anders Yeo
Alexey Zverovich
Counting in Mobile Networks: Theory and Experimentation	95	(15)
Kostas Hatzis
George Pentaris
Paul Spirakis
Basil Tampakas
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport	110	(14)
Frank Schulz
Dorothea Wagner
Karsten Weihe
Implementation and Experimental Evaluation of Graph Connectivity Algorithms Using LEDA	124	(15)
Panagiota Fatourou
Paul Spirakis
Panagiotis Zarafidis
Anna Zoura
On-Line Zone Construction in Arrangements of Lines in the Plane	139	(15)
Yuval Aharoni
Dan Halperin
Iddo Hanniel
Sariel Har-Peled
Chaim Linhart
The Design and Implementation of Planar Maps in Cgal	154	(15)
Eyal Flato
Dan Halperin
Ido Hanniel
Oren Nechushtan
An Easy to Use Implementation of Linear Perturbations within Cgal	169	(14)
Jochen Comes
Mark Ziegelmann
Analysing Cache Effects in Distribution Sorting	183	(15)
Naila Rahman
Rajeev Raman
Fast Regular Expression Search	198	(15)
Gonzalo Navarro
Mathieu Raffinot
An Experimental Evaluation of Hybrid Data Structures for Searching	213	(15)
Maureen Korda
Rajeev Raman
LEDA-SM: Extending LEDA to Secondary Memory	228	(15)
Andreas Crauser
Kurt Mehlhorn
A Priority Queue Transform	243	(15)
Michael L. Fredman
Implementation Issues and Experimental Study of a Wavelength Routing Algorithm for Irregular All-Optical Networks	258	(13)
Athanasios Bouganis
Ioannis Caragiannis
Christos Kaklamanis
Estimating Large Distances in Phylogenetic Reconstruction	271	(15)
Daniel H. Huson
Kelly Ann Smith
Tandy J. Warnow
The Performance of Concurrent Red-Black Tree Algorithms	286	(15)
Sobine Hanke
Performance Engineering Case Study: Heap Construction	301	(15)
Jesper Bojesen
Jyrki Katajainen
Maz Spork
A Fast and Simple Local Search for Graph Coloring	316	(14)
Massimiliano Caramia
Paolo Dell's Olmo
BALL: Biochemical Algorithms Library	330	(15)
Nicolas Boghossian
Oliver Kohlbacher
Hans-Peter Lenhof
An Experimental Study of Priority Queues in External Memory	345	(16)
Klaus Brengel
Andreas Crauser
Paolo Ferragina
Ulrich Meyer
Author Index	361