enter search term and/or author name
Engineering graph clustering: Models and experimental evaluation
Article No.: 1.1
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
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...
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
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...
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
We have conducted an extensive experimental study on algorithms for fully dynamic transitive closure. We have implemented the recent fully dynamic algorithms by King , Roditty , Roditty and Zwick [2002,...
Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks
Article No.: 1.7
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
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
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
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
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...
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
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
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
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...
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
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...
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
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...