ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 16, 2011



Section: 1 - Regular Papers

Motorcycle graphs: Stochastic properties motivate an efficient yet simple implementation
Stefan Huber, Martin Held
Article No.: 1.3
DOI: 10.1145/1963190.2019578

In this article, we study stochastic properties of a geometric setting that underpins random motorcycle graphs and use it to motivate a simple but very efficient algorithm for computing motorcycle graphs. An analysis of the mean trace length of...

Indexing methods for approximate dictionary searching: Comparative analysis
Leonid Boytsov
Article No.: 1.1
DOI: 10.1145/1963190.1963191

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

An experimental comparison of single-sided preference matching algorithms
Dimitrios Michail
Article No.: 1.4
DOI: 10.1145/1963190.2019579

We experimentally study the problem of assigning applicants to posts. Each 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...

Stable matching with couples: An empirical study
Péter Biró, Robert W. Irving, Ildikó Schlotter
Article No.: 1.2
DOI: 10.1145/1963190.1970372

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

Effective out-of-core parallel delaunay mesh refinement using off-the-shelf software
Andriy Kot, Andrey N. Chernikov, Nikos P. Chrisochoides
Article No.: 1.5
DOI: 10.1145/1963190.2019580

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

Limited discrepancy search revisited
Patrick Prosser, Chris Unsworth
Article No.: 1.6
DOI: 10.1145/1963190.2019581

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

Generating constrained random graphs using multiple edge switches
Lionel Tabourier, Camille Roth, Jean-Philippe Cointet
Article No.: 1.7
DOI: 10.1145/1963190.2063515

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

Approximation algorithms for speeding up dynamic programming and denoising aCGH data
Charalampos E. Tsourakakis, Richard Peng, Maria A. Tsiarli, Gary L. Miller, Russell Schwartz
Article No.: 1.8
DOI: 10.1145/1963190.2063517

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

Section: 1 - Regular Papers

Preface
Jan Vahrenhold
Article No.: 2.1
DOI: 10.1145/1963190.1970374

Computing elevation maxima by searching the gauss sphere
Bei Wang, Herbert Edelsbrunner, Dmitriy Morozov
Article No.: 2.2
DOI: 10.1145/1963190.1970375

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

Multilevel local search algorithms for modularity clustering
Randolf Rotta, Andreas Noack
Article No.: 2.3
DOI: 10.1145/1963190.1970376

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

psort, yet another fast stable sorting software
Paolo Bertasi, Marco Bressan, Enoch Peserico
Article No.: 2.4
DOI: 10.1145/1963190.1970377

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

Section: 1 - Regular Papers

Guest editors' foreword
Irene Finocchi, John Hershberger
Article No.: 3.1
DOI: 10.1145/1963190.2025377

Theory and practice of monotone minimal perfect hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna
Article No.: 3.2
DOI: 10.1145/1963190.2025378

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

Quasirandom rumor spreading: An experimental analysis
Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
Article No.: 3.3
DOI: 10.1145/1963190.2025379

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

Four-dimensional hilbert curves for R-trees
Herman Haverkort, Freek V. Walderveen
Article No.: 3.4
DOI: 10.1145/1963190.2025380

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

Solving maximum flow problems on real-world bipartite graphs
Cosmin Silvestru Negrucşeri, Mircea BOGDAN Pacsoşi, Barbara Stanley, Clifford Stein, Cristian George Strat
Article No.: 3.5
DOI: 10.1145/1963190.2025381

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

Dealing with large hidden constants: engineering a planar steiner tree PTAS
Siamak Tazari, Matthias Müller-Hannemann
Article No.: 3.6
DOI: 10.1145/1963190.2025382

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