ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


In Memoriam: David S. Johnson
Catherine Mcgeoch
Article No.: 1.1e
DOI: 10.1145/2907073


Section: In Memoriam

Editorial, SEA 2014 Special Issue
Joachim Gudmundsson, Jyrki Katajainen
Article No.: 1.1
DOI: 10.1145/2854021

A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs
Martin Bergner, Marco E. LÜbbecke, Jonas T. Witt
Article No.: 1.2
DOI: 10.1145/2851492

The cut packing problem in an undirected graph is to find a largest cardinality collection of pairwise edge-disjoint cuts. We provide the first experimental study of this NP-hard problem that is interesting from a pure theorist’s viewpoint...

Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
David Coudert, Dorian Mazauric, Nicolas Nisse
Article No.: 1.3
DOI: 10.1145/2851494

Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical...

Evaluation of Labeling Strategies for Rotating Maps
Andreas Gemsa, Martin Nöllenburg, Ignaz Rutter
Article No.: 1.4
DOI: 10.1145/2851493

We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of feature points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with...

Customizable Contraction Hierarchies
Julian Dibbelt, Ben Strasser, Dorothea Wagner
Article No.: 1.5
DOI: 10.1145/2886843

We consider the problem of quickly computing shortest paths in weighted graphs. Often, this is achieved in two phases: (1) derive auxiliary data in an expensive preprocessing phase, and (2) use this auxiliary data to speed up the query phase. By...

Tree-Based Coarsening and Partitioning of Complex Networks
Roland Glantz, Henning Meyerhenke, Christian Schulz
Article No.: 1.6
DOI: 10.1145/2851496

A hierarchy of increasingly coarse versions of a network allows one to represent the network on multiple scales at the same time. Often, the elementary operation for generating a hierarchy on a network is merging adjacent vertices, an operation...

LCP Array Construction in External Memory
Juha Kärkkäinen, Dominik Kempa
Article No.: 1.7
DOI: 10.1145/2851491

One of the most important data structures for string processing—the suffix array—needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for...

Faster Compressed Suffix Trees for Repetitive Collections
Gonzalo Navarro, Alberto Ordóñez Pereira
Article No.: 1.8
DOI: 10.1145/2851495

Recent compressed suffix trees targeted to highly repetitive sequence collections reach excellent compression performance, but operation times are very high. We design a new suffix tree representation for this scenario that still achieves very low...

Section: In Memoriam

Practical Algorithms for Finding Extremal Sets
Martin Marinov, Nicholas Nash, David Gregg
Article No.: 1.9
DOI: 10.1145/2893184

The minimal sets within a collection of sets are defined as the ones that do not have a proper subset within the collection, and the maximal sets are the ones that do not have a proper superset within the collection. Identifying extremal sets is a...

An Empirical Study on Randomized Optimal Area Polygonization of Planar Point Sets
Jiju Peethambaran, Amal Dev Parakkat, Ramanathan Muthuganapathy
Article No.: 1.10
DOI: 10.1145/2896849

While random polygon generation from a set of planar points has been widely investigated in the literature, very few works address the construction of a simple polygon with minimum area (MINAP) or maximum area (MAXAP) from a set of fixed planar...

Numerical Algorithm for Pólya Enumeration Theorem
Conrad W. Rosenbrock, Wiley S. Morgan, Gus L. W. Hart, Stefano Curtarolo, Rodney W. Forcade
Article No.: 1.11
DOI: 10.1145/2955094

Although the Pólya enumeration theorem has been used extensively for decades, an optimized, purely numerical algorithm for calculating its coefficients is not readily available. We present such an algorithm for finding the number of unique...

Implementing Efficient All Solutions SAT Solvers
Takahisa Toda, Takehide Soh
Article No.: 1.12
DOI: 10.1145/2975585

All solutions SAT (AllSAT for short) is a variant of the propositional satisfiability problem. AllSAT has been relatively unexplored compared to other variants despite its significance. We thus survey and discuss major techniques of AllSAT...

ReHub: Extending Hub Labels for Reverse k-Nearest Neighbor Queries on Large-Scale Networks
Alexandros Efentakis, Dieter Pfoser
Article No.: 1.13
DOI: 10.1145/2990192

Quite recently, the algorithmic community has focused on solving multiple shortest-path query problems beyond simple vertex-to-vertex queries, especially in the context of road networks. Unfortunately, those advanced query-processing techniques...

Section: In Memoriam

Introduction to Special Issue ALENEX 2013
Peter Sanders, Norbert Zeh
Article No.: 2.1
DOI: 10.1145/2966922

Short and Simple Cycle Separators in Planar Graphs
Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, Christian Sommer
Article No.: 2.2
DOI: 10.1145/2957318

We provide an implementation of an algorithm that, given a triangulated planar graph with m edges, returns a simple cycle that is a 3/4-balanced separator consisting of at most &sqrt;8m edges. An efficient construction of a short and...

Inducing Suffix and LCP Arrays in External Memory
Timo Bingmann, Johannes Fischer, Vitaly Osipov
Article No.: 2.3
DOI: 10.1145/2975593

We consider full text index construction in external memory (EM). Our first contribution is an inducing algorithm for suffix arrays in external memory, which runs in sorting complexity. Practical tests show that this algorithm outperforms the...

Lazy Lempel-Ziv Factorization Algorithms
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
Article No.: 2.4
DOI: 10.1145/2699876

For decades the Lempel-Ziv (LZ77) factorization has been a cornerstone of data compression and string processing algorithms, and uses for it are still being uncovered. For example, LZ77 is central to several recent text indexing data structures...