Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 12, 2008

Section: 1 - Regular Papers

Engineering graph clustering: Models and experimental evaluation

Article No.: 1.1
DOI: 10.1145/1227161.1227162

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...

An efficient, versatile approach to suffix sorting
Michael A. Maniscalco, Simon J. Puglisi
Article No.: 1.2
DOI: 10.1145/1227161.1278374

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...

Symmetry breaking for pseudo-Boolean formulas
Fadi A. Aloul, Arathi Ramani, Igor L. Markov, Karem A. Sakallah
Article No.: 1.3
DOI: 10.1145/1227161.1278375

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...

Efficient IP table lookup via adaptive stratified trees with selective reconstructions
Marco Pellegrini, Giordano Fusco
Article No.: 1.4
DOI: 10.1145/1227161.1278376

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...

Dynamic spatial approximation trees
Gonzalo Navarro, Nora Reyes
Article No.: 1.5
DOI: 10.1145/1227161.1322337

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...

An experimental study of algorithms for fully dynamic transitive closure
Ioannis Krommidas, Christos Zaroliagis
Article No.: 16
DOI: 10.1145/1227161.1370597

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,...

Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks
Keqin Li
Article No.: 1.7
DOI: 10.1145/1227161.1370598

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,...

An experimental study of sorting and branch prediction
Paul Biggar, Nicholas Nash, Kevin Williams, David Gregg
Article No.: 1.8
DOI: 10.1145/1227161.1370599

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...

Terracost: Computing least-cost-path surfaces for massive grid terrains
Thomas Hazel, Laura Toma, Jan Vahrenhold, Rajiv Wickremesinghe
Article No.: 1.9
DOI: 10.1145/1227161.1370600

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...

A graph approach to the threshold all-against-all substring matching problem
Marina Barsky, Ulrike Stege, Alex Thomo, Chris Upton
Article No.: 1.10
DOI: 10.1145/1227161.1370601

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...

A dictionary implementation based on dynamic perfect hashing
Martin Dietzfelbinger, Martin Hühne, Christoph Weidling
Article No.: 1.11
DOI: 10.1145/1227161.1370602

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...

Section: 1 - Regular Papers

Lars Arge, Giuseppe F. Italiano
Article No.: 2.1
DOI: 10.1145/1227161.1227163

Engineering a cache-oblivious sorting algorithm
Gerth Stølting Brodal, Rolf Fagerberg, Kristoffer Vinther
Article No.: 2.2
DOI: 10.1145/1227161.1227164

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...

Sum-of-squares heuristics for bin packing and memory allocation
Michael A. Bender, Bryan Bradley, Geetha Jagannathan, Krishnan Pillaipakkamnatt
Article No.: 2.3
DOI: 10.1145/1227161.1227165

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...

Efficient models for timetable information in public transportation systems
Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis
Article No.: 2.4
DOI: 10.1145/1227161.1227166

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...

Faster placement of hydrogens in protein structures by dynamic programming
Andrew Leaver-Fay, Yuanxin Liu, Jack Snoeyink, Xueyi Wang
Article No.: 2.5
DOI: 10.1145/1227161.1227167

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...

Section: 1 - Regular Papers

Papers from ALENEX 2005
Camil Demetrescu, Roberto Tamassia
Article No.: 3.1
DOI: 10.1145/1227161.1402293

On the adaptiveness of Quicksort
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz
Article No.: 3.2
DOI: 10.1145/1227161.1402294

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...

An experimental study of different approaches to solve the market equilibrium problem
Bruno Codenotti, Benton Mccune, Sriram Pemmaraju, Rajiv Raman, Kasturi Varadarajan
Article No.: 3.3
DOI: 10.1145/1227161.1402295

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...

Better external memory suffix array construction
Roman Dementiev, Juha Kärkkäinen, Jens Mehnert, Peter Sanders
Article No.: 3.4
DOI: 10.1145/1227161.1402296

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...

Approximating the true evolutionary distance between two genomes
Krister M. Swenson, Mark Marron, Joel V. Earnest-Deyoung, Bernard M. E. Moret
Article No.: 3.5
DOI: 10.1145/1227161.1402297

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...