Latest Articles

## Editorial -- ESA 2016 Special Issue

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)

### 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

The Journal of Experimental Algorithmics (ISSN 1084-6654) 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.

##### Forthcoming Articles

We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false positive rate by presenting both a theoretical model for the false positive rate and simulations using both synthetic data sets and real packet traces.

Real-Time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

Given an urban road network and a set of origin-destination pairs, the traffic assignment problem asks for the traffic flow on each road segment. A common solution employs a feasible-direction method, where the direction-finding step requires many shortest-path computations. In this paper, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by building a traffic assignment procedure upon customizable contraction hierarchies (CCHs), revisiting and carefully engineering CCH customization and queries, and adapting CCHs to compute batched point-to-point shortest paths. Although motivated by the traffic assignment problem, our optimizations apply to CCHs in general. In contrast to previous work, our evaluation uses real-world production data for all parts of the input. On a metropolitan area encompassing more than 2.7 million inhabitants, we decrease the flow-pattern computation for a typical two-hour morning peak from 75.6 to 9.5 seconds on one core, and 3.1 seconds on a four-core commodity machine. This represents a speedup of 24 over the state of the art, and 500 over the Dijkstra-based baseline.

Multi-Level Steiner Trees

In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $\rho = \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.

#### Editorial - SEA 2018 Special Issue

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm. In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., 2^O(t) ) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., 2^O(t log t) ) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle.

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this paper we study two structural properties of these graph classes that are of particular importance in this context, namely the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide. We provide experimental evaluations of several algorithms that approximate these parameters on real-world graphs. On the theoretical side, we provide a new algorithm for uniform quasi-wideness with polynomial size guarantees in graph classes of bounded expansion and show a lower bound indicating that the guarantees of this algorithm are close to optimal in graph classes with fixed excluded minor.

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