Search ACM DL

Search Issue

enter search term and/or author name

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

**Preface**

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

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