ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 18, 2013



Section: 1 - Selected Papers from SEA 2010

Foreword to the special issue SEA 2010
Paola Festa
Article No.: 1.1
DOI: 10.1145/2444016.2444017

A hybrid dynamic programming approach to the biobjective binary knapsack problem
Charles Delort, Olivier Spanjaard
Article No.: 1.2
DOI: 10.1145/2444016.2444018

This article is devoted to a study of the impact of using bound sets in biobjective dynamic programming. This notion, introduced by Villareal and Karwan [1981], has been independently revisited by Ehrgott and Gandibleux [2007], as well as by Sourd...

Alternative routes in road networks
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck
Article No.: 1.3
DOI: 10.1145/2444016.2444019

We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding...

Minimum time-dependent travel times with contraction hierarchies
G. Veit Batz, Robert Geisberger, Peter Sanders, Christian Vetter
Article No.: 1.4
DOI: 10.1145/2444016.2444020

Time-dependent road networks are represented as weighted graphs, where the weight of an edge depends on the time one passes through that edge. This way, we can model periodic congestions during rush hour and similar effects. In this work we deal...

Dynamic graph clustering combining modularity and smoothness
Robert Görke, Pascal Maillard, Andrea Schumm, Christian Staudt, Dorothea Wagner
Article No.: 1.5
DOI: 10.1145/2444016.2444021

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. Since many contemporary networks are not static but evolve over time, traditional static approaches can...

Data structures resilient to memory faults: An experimental study of dictionaries
Umberto Ferraro-Petrillo, Fabrizio Grandoni, Giuseppe F. Italiano
Article No.: 1.6
DOI: 10.1145/2444016.2444022

We address the problem of implementing data structures resilient to memory faults, which may arbitrarily corrupt memory locations. In this framework, we focus on the implementation of dictionaries and perform a thorough experimental study using a...

Section: 1 - Selected Papers from SEA 2010

Compressed suffix trees: Efficient computation and storage of LCP-values
Simon Gog, Enno Ohlebusch
Article No.: 2.1
DOI: 10.1145/2444016.2461327

The suffix tree is a very important data structure in string processing, but typical implementations suffer from huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of...

A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
Stefan Canzar, Khaled Elbassioni, Julián Mestre
Article No.: 2.2
DOI: 10.1145/2444016.2493372

We study the interval constrained coloring problem, a combinatorial problem arising in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. The problem captures the...

Optimal selection and sorting via dynamic programming
Micha Hofri
Article No.: 2.3
DOI: 10.1145/2444016.2493373

We show how to find optimal algorithms for the selection of one or more order statistics over a small set of numbers, and as an extreme case, complete sorting. The criterion is using the smallest number of comparisons; separate derivations are...

Exact online two-dimensional pattern matching using multiple pattern matching algorithms
Charalampos S. Kouzinopoulos, Konstantinos G. Margaritis
Article No.: 2.4
DOI: 10.1145/2513148

Baker and Bird and Baeza-Yates and Regnier are two of the most efficient and widely used algorithms for exact online two-dimensional pattern matching. Both use the automaton of the Aho-Corasick multiple pattern matching algorithm to locate all the...

Faster reaction mapping through improved naming techniques
Tina M. Kouri, Dinesh P. Mehta
Article No.: 2.5
DOI: 10.1145/2532569

Automated reaction mapping is an important tool in cheminformatics where it may be used to classify reactions or validate reaction mechanisms. The reaction mapping problem is known to be NP-Hard and may be formulated as an optimization problem. In...

On branching rules for convex mixed-integer nonlinear optimization
Pierre Bonami, Jon Lee, Sven Leyffer, Andreas Wächter
Article No.: 2.6
DOI: 10.1145/2532568

Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the...

Section: 1 - Selected Papers from SEA 2010

Listing All Maximal Cliques in Large Sparse Real-World Graphs
David Eppstein, Maarten Löffler, Darren Strash
Article No.: 3.1
DOI: 10.1145/2543629

An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms
Chandrashekhar Nagarajan, David P. Williamson
Article No.: 3.2
DOI: 10.1145/2543628
In this article, we consider different incremental and hierarchical k-median algorithms with provable performance guarantees and compare their running times and quality of output solutions on different benchmark k-median datasets. We...