ACM Journal of Experimental Algorithmics

Given a connected, weighted, undirected graph G and a bound D, the bounded diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges. In Prim's ...

When ties and incomplete preference lists are permitted in the stable marriage and hospitals/residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-...

The construction of t-spanners of a given point set has received a lot of attention, especially from a theoretical perspective. In this article, we experimentally study the performance and quality of the most common construction algorithms for points in ...

In this article, we describe GPU-Quicksort, an efficient Quicksort algorithm suitable for highly parallel multicore graphics processors. Quicksort has previously been considered an inefficient sorting solution for graphics processors, but we show that ...

We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of its nodes whose removal divides the graph into two components of similar size. These algorithms are based on planar separator theorems, ...

We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is related to the underlying problem. We consider three optimization problems: the directed MAX-CUT problem ...

We present efficient algorithms to solve the Line Cover Problem exactly. In this NP-complete problem, the inputs are n points in the plane and a positive integer k, and we are asked to answer if we can cover these n points with at most k lines. Our ...

Motivated by recent work on algorithmic theory for nonlinear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solution of large instances of some of these difficult problems. Our methods primarily ...

Known algorithms for reconstructing a 2-manifold from a point sample in R³ are naturally based on decisions/predicates that take the geometry of the point sample into account. Facing the always present problem of round-off errors that easily compromise ...

The National Airspace System (NAS) is designed to accommodate a large number of flights over North America. For purposes of workload limitations for air traffic controllers, the airspace is partitioned into approximately 600 sectors; each sector is ...

During recent years, impressive speed-up techniques for Dijkstra's have been developed. Unfortunately, the most advanced techniques use bidirectional search, which makes it hard to use them in scenarios where a backward search is prohibited. Even worse, ...

Given an undirected graph G = (V,E) with edge weights and a positive integer number k, the k-cardinality tree problem consists of finding a subtree T of G with exactly k edges and the minimum possible weight. Many algorithms have been proposed to solve ...

Ranking is a fundamental activity for organizing and, later, understanding data. Advice of the form “a should be ranked before b” is given. If this advice is consistent, and complete, then there is a total ordering on the data and the ranking problem is ...

This is an experimental study of algorithms for the shortest-path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more ...

We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In ...

A sequence of objects that are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces costs. A reordering buffer, which is a ...

The crossing number of a graph G is the smallest number of edge crossings in any drawing of G into the plane. Recently, the first branch-and-cut approach for solving the crossing number problem has been presented in Buchheim et al. [2005]. Its major ...

We present three cache-conscious implementations of STL standard compliant lists. Until now, one could either find simple doubly linked list implementations that easily cope with standard strict requirements, or theoretical approaches that do not take ...

Proximity searching consists of retrieving from a database those elements that are similar to a query object. The usual model for proximity searching is a metric space where the distance, which models the proximity, is expensive to compute. An index ...

The intersection of large ordered sets is a common problem in the context of the evaluation of boolean queries to a search engine. In this article, we propose several improved algorithms for computing the intersection of sorted arrays, and in particular ...

Suffix tree is one of the most important data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes ...

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize the amplitude of the electrical current flowing through the diodes, which has a direct impact on the lifetime of such a display. The ...

A Bloom filter is a very compact data structure that supports approximate membership queries on a set, allowing false positives.

We propose several new variants of Bloom filters and replacements with similar functionality. All of them have a better ...

Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining connectivity information in logarithmic time, they can support aggregation of information over paths, trees, or both. We ...

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within, at most,...