Latest Articles

## Analysis of a High-Performance TSP Solver on the GPU

Graphical Processing Units have been applied to solve NP-hard problems with no known polynomial time solutions. An example of such a problem is the... (more)

## Graph Bisection with Pareto Optimization

We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto sense. Our core algorithm heuristically solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core... (more)

## Complexity of Coloring Random Graphs: An Experimental Study of the Hardest Region

It is known that the problem of deciding k-colorability of a graph exhibits an easy-hard-easy pattern,—that is, the average-case complexity for backtrack-type algorithms, as a function of k, has a peak. This complexity peak is either at k = χ − 1 or k = χ, where χ is the chromatic number of the graph.... (more)

## Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality

Betweenness Centrality (BC) is a widely used metric of the relevance of a node in a network. The fastest-known algorithm for the evaluation of BC on... (more)

Betweenness is a well-known centrality measure that ranks the nodes according to their participation... (more)

## Updating Dynamic Random Hyperbolic Graphs in Sublinear Time

Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for... (more)

## Connection Scan Algorithm

We introduce the Connection Scan Algorithm (CSA) to efficiently answer queries to timetable information systems. The input consists, in the simplest setting, of a source position and a desired target position. The output consists of a sequence of vehicles such as trains or buses that a traveler should take to get from the source to the target. We... (more)

## Practical Minimum Cut Algorithms

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s... (more)

## Constructing a High-Dimensional kNN-Graph Using a Z-Order Curve

Although many fast methods exist for constructing a kNN-graph for low-dimensional data, it is still an open question how to do it efficiently for... (more)

## Computing Critical Nodes in Directed Graphs

We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graph G and a parameter k, we wish to remove a subset S of at most k vertices of G such that the residual graph G∖S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in... (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 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.

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

The BT algorithm of Bouchitt\'e and Todinca based on enumerating potential maximal cliques, originally proposed for the treewidth and minimum fill-in problems, yields improved exact exponential-time algorithms for various graph optimization problems related to optimal triangulations. While the BT algorithm has received significant attention in terms of theoretical analysis, less attention has been paid on engineering efficient implementations of the algorithm for different problems and thereby on empirical studies on its effectiveness in practice. In this work, we provide an experimental evaluation of an implementation of the BT algorithm, based on our second place winning entry in the 2nd Parameterized Algorithms and Computational Experiments Challenge (PACE 2017), extended to several related graph problems: treewidth, minimum fill-in, generalized and fractional hypertreewidth, and the total table size problem. Based on the results, we conclude that an efficient implementation of the BT algorithm yields an empirically competitive approach to each of the considered problems when compared to available implementations of alternative problem-specific algorithmic approaches.

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 parameter increases. Starting with the \emph{Sparse Rips filtration} introduced by Sheehy, some existing methods aim to reduce the size of the complex so as to improve the time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high dimensional data. In this paper, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called \emph{SimBa}, for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch collapse strategy as well as a new sparse Rips-like filtration. We experiment on a variety of low and high dimensional data sets. We show that our strategy presents a significant size reduction, and our algorithm for approximating Rips filtration persistence is order of magnitude faster than existing methods in practice.

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 e 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for k. However, the running time is also exponentially dependent on k, so only small k are tractable in practice. We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact LP-based algorithm, and to fast and simple 2-approximations.

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 suffix array in external memory. Experiments demonstrate that the new algorithms are about a factor of two faster than the fastest previous algorithm. We then further engineer the two new algorithms and improve them in three ways. First, we speed up the algorithms by up to a factor of two through parallelism. Just 8 threads is sufficient for making the algorithms essentially I/O bound. Second, we reduce the disk space usage of the algorithms making them in-place: The input (text and suffix array) is treated as read-only and the working disk space never exceeds the size of the final output (the LCP array). Third, we add support for large alphabets. All previous implementations assume the byte alphabet.

#### Editorial ESA 2016 Special Issue

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 quadratic worst-case running time, our algorithm exhibits a sublinear behaviour. We also propose some practical improvements of our algorithm and a variant with a linear worst-case time complexity. Experimental results show that, in most cases, some of the variants of our algorithm obtain the best running times when compared, under various conditions, against the most effective algorithms present in literature. For instance, in the case of small alphabets and long patterns, the gain in running time is up to 18%. This makes our proposed algorithm one of the most flexible solutions in practical cases.

Fully Dynamic 2-Hop Cover Labeling

The 2-hop-cover labeling of a graph is currently the best data structure for answering to 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 suitable in dynamic networks since after a network change: i) queries on the distance can return incorrect values; and ii) recomputing the labeling from scratch yields unsustainable time overhead. In this paper, we overcome this limit by introducing the first decremental algorithm able to update 2-hop-cover labelings under node/edge removals and edge weight increases. We prove the new algorithm to be: i) correct, i.e., after each update operation queries on the updated labeling return exact values; ii) efficient w.r.t. the number of nodes that change their distance as a consequence of a graph update; iii) able to preserve the minimality of the labeling, a desirable property that impacts on both query time and space occupancy. Furthermore, we provide an extensive experimental study to demonstrate the effectiveness of the new method. We consider it both alone and in combination with the unique known incremental approach~\cite{AIY14}, thus obtaining the first fully dynamic algorithm for updating 2-hop-cover labelings under general graph updates. Our experiments show that the new dynamic algorithms are able orders of magnitude faster than the from scratch approach while generating labelings that are equivalent, in terms of query time and space occupancy, to those computed from scratch, thus making 2-hop-cover labelings suited to be used in practice

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contribution, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time $|E|^{\frac{1}{2}+o(1)}$ with high probability, obtaining a significant speedup with respect to the $\Theta(|E|)$ worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the $k$ most central nodes. Furthermore, our analysis is general, and it might be extended to other settings.
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 address this problem by partially decoupling control from data flow: in order to perform the partitioning, we split the input in blocks of constant size; then, all elements in one block are compared with the pivot and the outcomes of the comparisons are stored in a buffer. In a second pass, the respective elements are rearranged. By doing so, we avoid conditional branches based on outcomes of comparisons (except for the final Insertionsort). Moreover, we prove that when sorting $n$ elements the average total number of branch mispredictions is at most $\epsilon n \log n + \Oh(n)$ for some small $\epsilon$ depending on the block size. Our experimental results are promising: when sorting random integer data, we achieve an increase in speed (number of elements sorted per second) of more than 80% over the GCC implementation of Quicksort (C++ std::sort). Also for many other data types and non-random inputs, there is still a significant speedup. Only in few special cases like (almost) sorted inputs, std::sort can beat our implementation. Moreover, on random input permutations, our implementation is even slightly faster than Super Scalar Sample Sort, which uses a linear amount of additional space. Finally, we also apply our approach to Quickselect and we obtain a speed-up of more than 100% over the GCC implementation (C++ std::nth_element).