Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 13, 2009

Section: 1 - Regular Papers

A backtracking-based algorithm for hypertree decomposition
Georg Gottlob, Marko Samer
Article No.: 1
DOI: 10.1145/1412228.1412229

Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem....

Implementing the LZ-index: Theory versus practice
Gonzalo Navarro
Article No.: 2
DOI: 10.1145/1412228.1412230

The LZ-index is a theoretical proposal of a lightweight data structure for text indexing, based on the Ziv-Lempel trie. If a text of u characters over an alphabet of size σ is compressible to n symbols using the LZ78 algorithm,...

Computing an approximation of the 1-center problem on weighted terrain surfaces
Mark A. Lanthier, Doron Nussbaum, Tsuo-Jung Wang
Article No.: 3
DOI: 10.1145/1412228.1412231

In this article, we discuss the problem of determining a meeting point of a set of scattered robots R &equls; {r1, r2,…,rs} in a weighted terrain P, which has n >...

Multilevel algorithms for linear ordering problems
Ilya Safro, Dorit Ron, Achi Brandt
Article No.: 4
DOI: 10.1145/1412228.1412232

Linear ordering problems are combinatorial optimization problems that deal with the minimization of different functionals by finding a suitable permutation of the graph vertices. These problems are widely used and studied in many practical and...

Computing visibility on terrains in external memory
Herman Haverkort, Laura Toma, Yi Zhuang
Article No.: 5
DOI: 10.1145/1412228.1412233

Given an arbitrary viewpoint v and a terrain, the visibility map or viewshed of v is the set of points in the terrain that are visible from v. In this article we consider the problem of computing the viewshed of a point on a...

A general buffer scheme for the windows scheduling problem
Amotz Bar-Noy, Richard E. Ladner, Jacob Christensen, Tami Tamir
Article No.: 6
DOI: 10.1145/1412228.1412234

Broadcasting is an efficient alternative to unicast for delivering popular on-demand media requests. Broadcasting schemes that are based on windows scheduling algorithms provide a way to satisfy all requests with both low bandwidth and low...

Multiword atomic read/write registers on multiprocessor systems
Andreas Larsson, Anders Gidenstam, Phuong H. Ha, Marina Papatriantafilou, Philippas Tsigas
Article No.: 7
DOI: 10.1145/1412228.1455262

Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for...

Succinct backward-DAWG-matching
Kimmo Fredriksson
Article No.: 8
DOI: 10.1145/1412228.1455263

We consider single and multiple string matching in small space and optimal average time. Our algorithm is based on the combination of compressed self-indexes and Backward-DAWG-Matching (BDM) algorithm. We consider several implementation techniques...

Efficiently implementing maximum independent set algorithms on circle graphs
Nicholas Nash, Sylvain Lelait, David Gregg
Article No.: 9
DOI: 10.1145/1412228.1455265

Circle graphs are an important class of graph with applications in a number of areas, including compiler optimization, VLSI design and computational geometry. In this article, we provide an experimental evaluation of the two most efficient...

Fast computation of empirically tight bounds for the diameter of massive graphs
Clémence Magnien, Matthieu Latapy, Michel Habib
Article No.: 10
DOI: 10.1145/1412228.1455266

The diameter of a graph is among its most basic parameters. Since a few years ago, it moreover became a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing...

Inversion-sensitive sorting algorithms in practice
Amr Elmasry, Abdelrahman Hammad
Article No.: 11
DOI: 10.1145/1412228.1455267

We study the performance of the most practical inversion-sensitive internal sorting algorithms. Experimental results illustrate that adaptive AVL sort consumes the fewest number of comparisons unless the number of inversions is less than...

Compressed text indexes: From theory to practice
Paolo Ferragina, Rodrigo González, Gonzalo Navarro, Rossano Venturini
Article No.: 12
DOI: 10.1145/1412228.1455268

A compressed full-text self-index represents a text in a compressed form and still answers queries efficiently. This represents a significant advancement over the (full-)text indexing techniques of the previous decade, whose indexes...

A domain decomposition algorithm for constraint satisfaction
Wady Naanaa
Article No.: 13
DOI: 10.1145/1412228.1455269

This article presents a domain decomposition algorithm for solving constraint satisfactions problems (CSPs). The proposed algorithm relies on a weak form of neighborhood substitutability referred to as directional substitutability. The main idea...

An improved heuristic for computing short integral cycle bases
Telikepalli Kavitha, Katakam Vamsi Krishna
Article No.: 14
DOI: 10.1145/1412228.1498696

In this article, we consider the problem of constructing low-weight integral cycle bases in a directed graph G = (V, E) with nonnegative edge weights. It has been shown that low-weight integral cycle bases have...

Automated reaction mapping
John D. Crabtree, Dinesh P. Mehta
Article No.: 15
DOI: 10.1145/1412228.1498697

Automated reaction mapping is a fundamental first step in the analysis of chemical reactions and opens the door to the development of sophisticated chemical kinetic tools. This article formulates the reaction mapping problem as an optimization...

Section: 1 - Regular Papers

Rajeev Raman, Matt Stallmann
Article No.: 1
DOI: 10.1145/1412228.1412235

Data reduction and exact algorithms for clique cover
Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier
Article No.: 2
DOI: 10.1145/1412228.1412236

To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm,...

An experimental study of point location in planar arrangements in CGAL
Idit Haran, Dan Halperin
Article No.: 3
DOI: 10.1145/1412228.1412237

We study the performance in practice of various point-location algorithms implemented in CGAL (the Computational Geometry Algorithms Library), including a newly devised landmarks algorithm. Among the other algorithms studied are: a...

Summarizing spatial data streams using ClusterHulls
John Hershberger, Nisheeth Shrivastava, Subhash Suri
Article No.: 4
DOI: 10.1145/1412228.1412238

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional (2D) points, how can we summarize its spatial distribution or shape using a small, bounded amount of memory? We propose a novel scheme,...

Engineering multilevel overlay graphs for shortest-path queries
Martin Holzer, Frank Schulz, Dorothea Wagner
Article No.: 5
DOI: 10.1145/1412228.1412239

An overlay graph of a given graph G = (V, E) on a subset SV is a graph with vertex set S and edges corresponding to shortest paths in G. In particular, we consider variations of the...