ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 4, 1999

A memetic algorithm to schedule planned maintenance for the national grid
E. K. Burke, A. J. Smith
Article No.: 1
DOI: 10.1145/347792.347801
The combination of local search operators, problem specific information and a genetic algorithm has provided very good results in certain scheduling problems, particularly in timetabling and maintenance scheduling problems. The resulting algorithm...

A new string-pattern matching algorithm using partitioning and hashing efficiently
Sun Kim
Article No.: 2
DOI: 10.1145/347792.347803
In this paper, we present a new string-pattern matching algorithm that partitions the text into segments of the input pattern length and searches for pattern occurrences using a simple hashing scheme. Unlike the well known Boyer-Moore style...

Matrix multiplication: a case study of enhanced data cache utilization
N. Eiron, M. Rodeh, I. Steinwarts
Article No.: 3
DOI: 10.1145/347792.347806
Modern machines present two challenges to algorithm engineers and compiler writers: They have superscalar, super-pipelined structure, and they have elaborate memory subsystems specifically designed to reduce latency and increase bandwidth. Matrix...

Efficient implementation of an optimal greedy algorithm for wavelength assignment in directed tree networks
T. Erlebach, K. Jansen
Article No.: 4
DOI: 10.1145/347792.347808
In all-optical networks with wavelength-division multiplexing several connections can share a physical link if the signals are transmitted on different wavelengths. As the number of available wavelengths is limited in practice, it is important to...

Hybrid tree reconstruction methods
D. Huson, S. Nettles, K. Rice, T. Warnow, S. Yooseph
Article No.: 5
DOI: 10.1145/347792.347812
A major computational problem in biology is the reconstruction of evolutionary trees for species sets, and accuracy is measured by comparing the topologies of the reconstructed tree and the model tree. One of the major debates in the field is whether...

A computational study of routing algorithms for realistic transportation networks
R. Jacob, M. Marathe, K. Nagel
Article No.: 6
DOI: 10.1145/347792.347814
We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation ANalysis and SIMulation System) project. The main focus of the paper is to study how various heuristic...

Implementing weighted b-matching algorithms: towards a flexible software design
M. Müller-Hannemann, A. Schwartz
Article No.: 7
DOI: 10.1145/347792.347815
We present a case study on the design of an implementation of a fundamental combinatorial optimization problem: weighted <i>b</i>-matching. Although this problem is well-understood in theory and efficient algorithms are known, only little...

Computing the width of a three-dimensional point set: an experimental study
J. Schwerdt, M. Smid, J. Majhi, R. Janardan
Article No.: 8
DOI: 10.1145/347792.347816
We describe a robust, exact, and efficient implementation of an algorithm that computes the width of a three-dimensional point set. The algorithm is based on efficient solutions to problems that are at the heart of computational geometry:...