Algorithm Engineering: 4th International Workshop, Wae 2000, Saarbrucken, Germany, September 2000 : Proceedings

by Naher, Stefan; Wagner, Dorothea

• ISBN13: 9783540425120
• ISBN10: 3540425128
• Format: Paperback
• Copyright: 2001-10-01
• Publisher: Springer Verlag

Summary

This book constitutes the thoroughly refereed post-proceedings of the 4th International Workshop on Algorithm Engineering, WAE 2000, held in Saarbrücken, Germany in September 2000. The 19 revised full papers presented together with one invited paper were carefully reviewed and selected from a total of 30 submissions. Among the topics addressed are software repositories allowing for the use and experimentation with efficient discrete algorithms; novel uses of discrete algorithms; methodological issues on algorithms and data structures; and methodological issues on converting user requirements into efficient algorithmic and implementation solutions.

Table of Contents

Invited Lectures
On the differences between ``Practical'' and ``Applied''	1	(10)
Karsten Weihe
Contributed Papers
An Experimental Study of Online Scheduling Algorithms	11	(12)
Susanne Albers
Bianca Schroder
Implementation of O(nm log n) Weighted Matchings in General Graphs. The Power of Data Structures	23	(16)
Kurt Mehlhorn
Guido Schafer
Pushing the Limits in Sequential Sorting	39	(12)
Stefan Edelkamp
Patrick Stiegeler
Efficient Sorting Using Registers and Caches	51	(12)
Lars Arge
Jeff Chase
Jeffrey S. Vitter
Rajiv Wickremesinghe
Lattice Basis Reduction with Dynamic Approximation	63	(11)
Werner Backes
Susanne Wetzel
Clustering Data Without Prior Knowledge	74	(13)
Javed Aslam
Alain Leblanc
Clifford Stein
Recognizing Bundles in Time Table Graphs - A Structural Approach	87	(12)
Annegret Liebers
Karsten Weihe
Analysis and Experimental Evaluation of an Innovative and Efficient Routing Protocol for Ad-hoc Mobile Networks	99	(12)
I. Chatzigiannakis
S. Nikoletseas
P. Spirakis
Portable List Ranking: An Experimental Study	111	(12)
Isabelle Guerin Lassous
Jens Gustedt
Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM	123	(12)
Kazuo Iwama
Daisuke Kawai
Shuichi Miyazaki
Yasuo Okabe
Jun Umemoto
Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms	135	(12)
Peter Sanders
Rudolf Fleischer
Visualizing Algorithms over the Web with the Publication-Driven Approach	147	(12)
Camil Demetrescu
Irene finocchi
Giuseppe Liotta
Interchanging Two Segments of an Array in a Hierarchical Memory System	159	(12)
Jesper Bojesen
Jyrki Katajainen
Two-Dimensional Arrangements in CGAL and Adaptive Point Location for Parametric Curves	171	(12)
Iddo Hanniel
Dan Halperin
Planar Point Location for Large Data Sets: To Seek or Not to Seek	183	(12)
Jan Vahrenhold
Klaus H. Hinrichs
Implementation of Approximation Algorithms for Weighted and Unweighted Edge-Disjoint Paths in Bidirected Trees	195	(12)
Thomas Erlebach
Klaus Jansen
Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees	207	(11)
Guido Proietti
Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study	218	(12)
Camil Demetrescu
Daniele Frigioni
Alberto Marchetti-Spaccamela
Umberto Nanni
New Algorithms for Examination Timetabling	230	(13)
Massimiliano Caramia
Paolo Dell'Olmo
Giuseppe F. Italiano
Author Index	243