ACM Journal of Experimental Algorithmics

simple but very efficient algorithm for computing motorcycle graphs. An analysis of the mean trace length of n random motorcycles suggests that, on average, a motorcycle crosses only a constant number of cells within a √ n × √ n rectangular grid, ...

The primary goal of this article is to survey state-of-the-art indexing methods for approximate dictionary searching. To improve understanding of the field, we introduce a taxonomy that classifies all methods into direct methods and sequence-based ...

In practical applications, algorithms for the classic version of the hospitals residents problem (the many-one version of the stable marriage problem) may have to be extended to accommodate the needs of couples who wish to be allocated to (...

applicant provides a preference list, which may contain ties, ranking a subset of the posts. Different optimization criteria may be defined, which depend on the desired solution properties. The main focus of this work is to assess the quality of ...

We present three related out-of-core parallel mesh generation algorithms and their implementations for small size computational clusters. Computing out-of-core permits to solve larger problems than otherwise possible on the same hardware setup. Also, ...

Harvey and Ginsberg's limited discrepancy search (LDS) is based on the assumption that costly heuristic mistakes are made early in the search process. Consequently, LDS repeatedly probes the state space, going against the heuristic (i.e., taking ...

The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints (e.g., degree distributions). However, in general, it is not necessarily possible to access ...

The development of cancer is largely driven by the gain or loss of subsets of the genome, promoting uncontrolled growth or disabling defenses against it. Denoising array-based Comparative Genome Hybridization (aCGH) data is an important computational ...

The elevation function on a smoothly embedded 2-manifold in ℝ³ reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting the ...

Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton clusters ...

psort is the fastest sorting software according to the PennySort benchmark, sorting 181GB of data in 2008 and 224GB in 2009 for $0.01 of computer time. This article details its internals, and the careful fitting of its architecture to the structure of ...

Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions (Fox et al. 1991) have been used to retrieve the position of a key in a given ...

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round, each informed node informs a random neighbor. In the recently proposed ...

Two-dimensional R-trees are a class of spatial index structures in which objects are arranged to enable fast window queries: report all objects that intersect a given query window. One of the most successful methods of arranging the objects in the index ...

In this article, we present an experimental study of several maximum-flow algorithms in the context of unbalanced bipartite networks. Our experiments are motivated by a real-world problem of managing reservation-based inventory in Google content ad ...

We present the first attempt on implementing a highly theoretical polynomial-time approximation scheme (PTAS) with huge hidden constants, namely, the PTAS for Steiner tree in planar graphs by Borradaile, Klein, and Mathieu (2009). Whereas this result, ...