Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 19, 2014

Section: Regular Papers

Locally Compressed Suffix Arrays
Rodrigo González, Gonzalo Navarro, Héctor Ferrada
Article No.: 1.1
DOI: 10.1145/2594408

We introduce a compression technique for suffix arrays. It is sensitive to the compressibility of the text and local, meaning that random portions of the suffix array can be decompressed by accessing mostly contiguous memory areas. This...

Randomized Rounding in the Presence of a Cardinality Constraint
Benjamin Doerr, Magnus Wahlström
Article No.: 1.2
DOI: 10.1145/2594409

We consider the problem of generating randomized roundings that satisfy a single cardinality constraint and admit Chernoff-type large deviation bounds for weighted sums of the variables. That this can be done efficiently was proven by Srinivasan...

Efficient Matching for Column Intersection Graphs
B. O. Fagginger Auer, R. H. Bisseling
Article No.: 1.3
DOI: 10.1145/2616587

To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-quality matchings in column intersection graphs of large sparse binary matrices. We show that such algorithms have a natural decomposition in an...

Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions
Claudio Angione, Annalisa Occhipinti, Giuseppe Nicosia
Article No.: 1.4
DOI: 10.1145/2629498

Recent studies in theoretical computer science have exploited new algorithms and methodologies based on statistical physics for investigating the structure and the properties of the Satisfiability (SAT) problem. We propose a characterization of...

An Experimental Study on Approximating k Shortest Simple Paths
Asaf Frieder, Liam Roditty
Article No.: 1.5
DOI: 10.1145/2630068

We have conducted an extensive experimental study on approximation algorithms for computing k shortest simple paths in weighted directed graphs. Very recently, Bernstein [2010] presented an algorithm that computes a 1 + ϵ...

An Audit Tool for Genome Rearrangement Algorithms
Gustavo Rodrigues Galvão, Zanoni Dias
Article No.: 1.7
DOI: 10.1145/2661633

We consider the combinatorial problem of sorting a permutation using a minimum number of rearrangement events, which finds application in the estimation of evolutionary distance between species. Many variants of this problem, which we generically...

On a Model of Virtual Address Translation
Tomasz Jurkiewicz, Kurt Mehlhorn
Article No.: 1.9
DOI: 10.1145/2656337

Modern computers are not Random Access Machines (RAMs). They have a memory hierarchy, multiple cores, and a virtual memory. We address the computational cost of the address translation in the virtual memory. The starting point for our work on...

Section: Special Issue SEA 2012

Ralf Klasing
Article No.: 2.1
DOI: 10.1145/2677196

Advanced Coarsening Schemes for Graph Partitioning
Ilya Safro, Peter Sanders, Christian Schulz
Article No.: 2.2
DOI: 10.1145/2670338

The graph partitioning problem is widely used and studied in many practical and theoretical applications. Today, multilevel strategies represent one of the most effective and efficient generic frameworks for solving this problem on large-scale...

General Document Retrieval in Compact Space
Gonzalo Navarro, Simon J. Puglisi, Daniel Valenzuela
Article No.: 2.3
DOI: 10.1145/2670128

Given a collection of documents and a query pattern, document retrieval is the problem of obtaining documents that are relevant to the query. The collection is available beforehand so that a data structure, called an index, can be built on...

Engineering Efficient Paging Algorithms
Gabriel Moruz, Andrei Negoescu, Christian Neumann, Volker Weichert
Article No.: 2.4
DOI: 10.1145/2670127

In the field of online algorithms, paging is a well-studied problem. LRU is a simple paging algorithm that incurs few cache misses and supports efficient implementations. Algorithms outperforming LRU in terms of cache misses exist but are in...

Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks
Dominik Kirchler, Leo Liberti, Roberto Wolfler Calvo
Article No.: 2.5
DOI: 10.1145/2670126

We consider shortest paths on time-dependent multimodal transportation networks in which restrictions or preferences on the use of certain modes of transportation may arise. We model restrictions and preferences by means of regular languages....

Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation
David F. Manlove, Gregg O’malley
Article No.: 2.6
DOI: 10.1145/2670129

We study the computational problem of identifying optimal sets of kidney exchanges in the UK. We show how to expand an integer programming-based formulation due to Roth et al. [2007] in order to model the criteria that constitute the UK definition...

Candidate Sets for Alternative Routes in Road Networks
Dennis Luxen, Dennis Schieferdecker
Article No.: 2.7
DOI: 10.1145/2674395

We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We...

Section: Special Issue ALENEX 2012

Introduction to Special Issue ALENEX'12
David A. Bader, Petra Mutzel
Article No.: 3.1
DOI: 10.1145/2721893

User-Constrained Multimodal Route Planning
Julian Dibbelt, Thomas Pajor, Dorothea Wagner
Article No.: 3.2
DOI: 10.1145/2699886

In the multimodal route planning problem, we are given multiple transportation networks (e.g., pedestrian, road, public transit) and ask for a best integrated journey between two points. The main challenge is that a seemingly optimal...

Experiments on Density-Constrained Graph Clustering
Robert Görke, Andrea Kappes, Dorothea Wagner
Article No.: 3.3
DOI: 10.1145/2638551

Clustering a graph means identifying internally dense subgraphs that are only sparsely interconnected. Formalizations of this notion lead to measures that quantify the quality of a clustering and to algorithms that actually find clusterings....

Fast Compressed Tries through Path Decompositions
Roberto Grossi, Giuseppe Ottaviano
Article No.: 3.4
DOI: 10.1145/2656332

Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. More than 50 years of usage have produced many variants and implementations to overcome some of their limitations....