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 <underline>Sim</underline>plicial <underline>Ba</underline>tch 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)

NEWS

JEA joins RCR: Replicated Computational Results Initiative

http://jea.acm.org/rcr_initiative.cfm

In Memoriam: David S. Johnson

http://dl.acm.org/citation.cfm?id=2907073

About JEA

The Journal of Experimental Algorithmics (ISSN 1084-6654) is a high-quality journal 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
Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments

Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.

Automated Congressional Redistricting

Every ten 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 last few decades, the growing capabilities of computers have offered the promise of objective, computerized redistricting. Unfortunately, the redistricting problem can be shown to be NP-Complete, but there are a number of approximation algorithms and heuristics that are effective. We specifically define the redistricting problem and analyze two new algorithms. By comparing our new algorithms based on compactness and population deviation to existing algorithms and the actual districts, we demonstrate the tradeoffs of different algorithm components. We extend an approximation algorithm for the capacitated k-center problem by Khuller and Sussmann to this redistricting problem and show that these modifications maintain their original 5-approximation bounds under some conditions. We also introduce a divide and conquer heuristic that produces redistricting plans with the optimal population deviation in most U.S. states. In experiments, we show that our divide and conquer heuristic produces the best population deviation but a worse compactness score than an existing simulated annealing approach by Olson. While the modified capacitated k-center approach offers guarantees under certain conditions, it tends to only produce valid plans in small states.

All ACM Journals | See Full Journal Index

Search JEA
enter search term and/or author name