Search ACM DL

Search Issue

enter search term and/or author name

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

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

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