enter search term and/or author name
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
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
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
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...
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
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...
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
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
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
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...
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...
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
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
Short and Simple Cycle Separators in Planar Graphs
Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, Christian Sommer
Article No.: 2.2
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...
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...
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...