ACM Journal of Experimental Algorithmics

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 as well as ...

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 and ...

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 one ...

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 adding ...

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 that can ...

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 constructing the LCP array ...

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 space ...

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

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 points. ...

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 colorings of ...

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 solvers. We ...

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 cannot ...

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 √8m edges. An efficient construction of a short and balanced separator that ...

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 previous ...

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 designed ...