ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 22, 2017

Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
Uwe Baier, Timo Beller, Enno Ohlebusch
Article No.: 1.1
DOI: 10.1145/3035540

A compressed suffix tree usually consists of three components: a compressed suffix array, a compressed LCP-array, and a succinct representation of the suffix tree topology. There are parallel algorithms that construct the suffix array and the...

Practical Compact Indexes for Top-k Document Retrieval
Simon Gog, Roberto Konow, Gonzalo Navarro
Article No.: 1.2
DOI: 10.1145/3043958

We present a fast and compact index for top-k document retrieval on general string collections, in which given a string pattern, the index returns the k documents where it appears most often. We adapt a linear-space and optimal-time...

Array Layouts for Comparison-Based Searching
Paul-Virak Khuong, Pat Morin
Article No.: 1.3
DOI: 10.1145/3053370

We attempt to determine the best order and search algorithm to store n comparable data items in an array, A, of length n so we can, for any query value, x, quickly find the smallest value in A that is greater...

Geometry Helps to Compare Persistence Diagrams
Michael Kerber, Dmitriy Morozov, Arnur Nigmetov
Article No.: 1.4
DOI: 10.1145/3064175

Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric...

Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
Tommi Hirvola, Jorma Tarhio
Article No.: 1.5
DOI: 10.1145/3129536

We consider approximate string matching of a circular pattern consisting of the rotations of a pattern of length m. From SBNDM and Tuned Shift-Add, we derive a sublinear-time algorithm for searching a noncircular pattern with k...

An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
Matthias Poloczek, David P. Williamson
Article No.: 1.6
DOI: 10.1145/3064174

We evaluate the performance of fast approximation algorithms for MAX SAT on the comprehensive benchmark sets from the SAT and MAX SAT contests. Our examination of a broad range of algorithmic techniques reveals that greedy algorithms offer...