Search ACM DL

Search Issue

enter search term and/or author name

Section:

**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 R ^{3}**

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 R^{3} 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,...