ACM Journal of Experimental Algorithmics

A promising approach to graph clustering is based on the intuitive notion of intracluster density versus intercluster sparsity. As for the weighted case, clusters should accumulate lots of weight, in contrast to their connection to the remaining graph, ...

Sorting the suffixes of a string into lexicographical order is a fundamental task in a number of contexts, most notably lossless compression (Burrows--Wheeler transformation) and text indexing (suffix arrays). Most approaches to suffix sorting produce a ...

Many important tasks in design automation and artificial intelligence can be performed in practice via reductions to Boolean satisfiability (SAT). However, such reductions often omit application-specific structure, thus handicapping tools in their ...

IP address lookup is a critical operation for high-bandwidth routers in packet-switching networks, such as Internet. The lookup is a nontrivial operation, since it requires searching for the longest prefix, among those stored in a (large) given table, ...

Metric space searching is an emerging technique to address the problem of efficient similarity searching in many applications, including multimedia databases and other repositories handling complex objects. Although promising, the metric space approach ...

We have conducted an extensive experimental study on algorithms for fully dynamic transitive closure. We have implemented the recent fully dynamic algorithms by King [1999], Roditty [2003], Roditty and Zwick [2002, 2004], and Demetrescu and Italiano [...

We investigate the problem of online routing and wavelength assignment and the related throughput maximization problem in wavelength division multiplexing optical networks. It is pointed out that these problems are highly inapproximable, that is, the ...

Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account ...

This paper addresses the problem of computing least-cost-path surfaces for massive grid terrains. Consider a grid terrain T and let C be a cost grid for T such that every point in C stores a value that represents the cost of traversing the corresponding ...

We present a novel graph model and an efficient algorithm for solving the “threshold all against all” problem, which involves searching two strings (with length M and N, respectively) for all maximal approximate substring matches of length at least S, ...

We describe experimental results on an implementation of a dynamic dictionary. The basis of our implementation is “dynamic perfect hashing” as described by Dietzfelbinger et al. (SIAM J. Computing 23, 1994, pp. 738--761), an extension of the storage ...

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort and compare the final ...

The sum-of-squares algorithm (SS) was introduced by Csirik, Johnson, Kenyon, Shor, and Weber for online bin packing of integral-sized items into integral-sized bins. First, we show the results of experiments from two new variants of the SS algorithm. The ...

We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach, every event at a station, e.g., the departure of a train, is modeled as a node in ...

M. Word and coauthors from the Richardsons' 3D Protein Structure laboratory at Duke University propose dot scores to measure interatomic interactions in molecular structures. Their program REDUCE uses these scores in a brute-force search to solve ...

Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming ...

Over the last few years, the problem of computing market equilibrium prices for exchange economies has received much attention in the theoretical computer science community. Such activity led to a flurry of polynomial time algorithms for various ...

Suffix arrays are a simple and powerful data structure for text processing that can be used for full text indexes, data compression, and many other applications, in particular, in bioinformatics. However, so far, it has appeared prohibitive to build ...

As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, duplications, deletions, and movements of genes ...