ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 14, 2009



Section: 1 - Regular Papers

Greedy heuristics for the bounded diameter minimum spanning tree problem
Bryant A. Julstrom
Article No.: 1
DOI: 10.1145/1498698.1498699

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

Finding large stable matchings
Robert W. Irving, David F. Manlove
Article No.: 2
DOI: 10.1145/1498698.1537595

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

Experimental study of geometric t-spanners
Mohammad Farshi, Joachim Gudmundsson
Article No.: 3
DOI: 10.1145/1498698.1564499

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

GPU-Quicksort: A practical Quicksort algorithm for graphics processors
Daniel Cederman, Philippas Tsigas
Article No.: 4
DOI: 10.1145/1498698.1564500

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

Engineering planar separator algorithms
Martin Holzer, Frank Schulz, Dorothea Wagner, Grigorios Prasinos, Christos Zaroliagis
Article No.: 5
DOI: 10.1145/1498698.1571635

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

Local search starting from an LP solution: Fast and quite good
Alaubek Avdil, Karsten Weihe
Article No.: 6
DOI: 10.1145/1498698.1594877

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

Reduction rules deliver efficient FPT-algorithms for covering points with lines
Vladimir Estivill-Castro, Apichat Heednacram, Francis Suraweera
Article No.: 7
DOI: 10.1145/1498698.1626535

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

Computation in multicriteria matroid optimization
Jesús A. De Loera, David C. Haws, Jon Lee, Allison O'Hair
Article No.: 8
DOI: 10.1145/1498698.1658383

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

Section: 1 - Regular Papers

Preface
J. Ian Munro, Dorothea Wagner
Article No.: 1
DOI: 10.1145/1498698.1537596

How much geometry it takes to reconstruct a 2-manifold in R3
Daniel Dumitriu, Stefan Funke, Martin Kutz, Nikola Milosavljević
Article No.: 2
DOI: 10.1145/1498698.1537597

Known algorithms for reconstructing a 2-manifold from a point sample in R3 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...

Geometric algorithms for optimal airspace design and air traffic controller workload balancing
Amitabh Basu, Joseph S. B. Mitchell, Girish Kumar Sabhnani
Article No.: 3
DOI: 10.1145/1498698.1537598

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

SHARC: Fast and robust unidirectional routing
Reinhard Bauer, Daniel Delling
Article No.: 4
DOI: 10.1145/1498698.1537599

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

Obtaining optimal k-cardinality trees fast
Markus Chimani, Maria Kandyba, Ivana Ljubić, Petra Mutzel
Article No.: 5
DOI: 10.1145/1498698.1537600

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

Ranking tournaments: Local search and a new algorithm
Tom Coleman, Anthony Wirth
Article No.: 6
DOI: 10.1145/1498698.1537601

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

Shortest-path feasibility algorithms: An experimental evaluation
Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, Renato F. Werneck
Article No.: 7
DOI: 10.1145/1498698.1537602

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

Section: 1 - Regular Papers

Preface to special section of selected papers from WEA 2006
Maria Serna, Carme Àlvarez
Article No.: 1
DOI: 10.1145/1498698.1564501

Goal-directed shortest-path queries using precomputed cluster distances
Jens Maue, Peter Sanders, Domagoj Matijevic
Article No.: 2
DOI: 10.1145/1498698.1564502

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

Evaluation of online strategies for reordering buffers
Matthias Englert, Heiko Röglin, Matthias Westermann
Article No.: 3
DOI: 10.1145/1498698.1564503

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

Experiments on exact crossing minimization using column generation
Markus Chimani, Carsten Gutwenger, Petra Mutzel
Article No.: 4
DOI: 10.1145/1498698.1564504

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

Lists revisited: Cache-conscious STL lists
Leonor Frias, Jordi Petit, Salvador Roura
Article No.: 5
DOI: 10.1145/1498698.1564505

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

Speeding up spatial approximation search in metric spaces
Karina Figueroa, Edgar Chavez, Gonzalo Navarro, Rodrigo Paredes
Article No.: 6
DOI: 10.1145/1498698.1564506

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

An experimental investigation of set intersection algorithms for text searching
Jérémy Barbay, Alejandro López-Ortiz, Tyler Lu, Alejandro Salinger
Article No.: 7
DOI: 10.1145/1498698.1564507

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

Section: 1 - Regular Papers

Preface
Camil Demetrescu
Article No.: 1
DOI: 10.1145/1498698.1594227

Engineering a compressed suffix tree implementation
N. Välimäki, V. Mäkinen, W. Gerlach, K. Dixit
Article No.: 2
DOI: 10.1145/1498698.1594228

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

Algorithms for longer OLED lifetime
Friedrich Eisenbrand, Andreas Karrenbauer, Chihao Xu
Article No.: 3
DOI: 10.1145/1498698.1594229

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

Cache-, hash-, and space-efficient bloom filters
Felix Putze, Peter Sanders, Johannes Singler
Article No.: 4
DOI: 10.1145/1498698.1594230

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

Dynamic trees in practice
Robert E. Tarjan, Renato F. Werneck
Article No.: 5
DOI: 10.1145/1498698.1594231

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

Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?
Vladimir Deineko, Alexander Tiskin
Article No.: 6
DOI: 10.1145/1498698.1594232

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