ACM DL

ACM Journal of

Experimental Algorithmics (JEA)

Menu
Latest Articles

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all... (more)

Better External Memory LCP Array Construction

The suffix array, perhaps the most important data structure in modern string processing, needs to be augmented with the longest-common-prefix (LCP) array in many applications. Their construction is often a major bottleneck, especially when the data is too big for internal memory. We describe two new algorithms for computing the LCP array from the... (more)

BlockQuicksort: Avoiding Branch Mispredictions in Quicksort

It is well known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions. We present a novel approach to addressing this problem by partially decoupling control from dataflow: in order to perform the partitioning, we split the input into... (more)

SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch Collapse

In topological data analysis, a point cloud data P extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on P indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale... (more)

Fully Dynamic 2-Hop Cover Labeling

The 2-hop Cover labeling of a graph is currently the best data structure for answering shortest-path distance queries on large-scale networks, since it combines low query times, affordable space occupancy, and reasonable preprocessing effort. Its main limit resides in not being suited for dynamic networks since, after a network change, (1) queries... (more)

Strong Steiner Tree Approximations in Practice

In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of k-restricted full components for some k ≥ 3. For most of the algorithms, their strongest theoretical... (more)

Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition

We present a simple and very efficient algorithm for string matching based on the combination of weak factor recognition and hashing. Despite its... (more)

Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté--Todinca Algorithm

The BT algorithm of Bouchitté and Todinca based on enumerating potential maximal cliques, originally proposed for the treewidth and minimum... (more)

Automated Congressional Redistricting

Every 10 years, when states are forced to redraw their congressional districts, the process is intensely partisan, and the outcome is rarely fair and democratic. In the past few decades, the growing capabilities of computers have offered the promise of objective, computerized redistricting. Unfortunately, the redistricting problem can be shown to... (more)

NEWS

About JEA

The Journal of Experimental Algorithmics is devoted to the study of discrete algorithms and data structures from an empirical perspective. The journal welcomes original submissions that focus on design, implementation, and performance evaluation through a combination of experimentation and classical techniques.

read more
Forthcoming Articles
A Generic Framework for Engineering Graph Canonization Algorithms

The state-of-the-art tools for practical graph canonization are all based on the indivi\-dualization-refinement paradigm, and their difference is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas affect the performance on different graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of different algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of different graph classes we investigate the effect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of difficult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

All ACM Journals | See Full Journal Index

Search JEA
enter search term and/or author name