Search ACM DL

Search Issue

enter search term and/or author name

**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;8*m* 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...