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: SECTION: 2 - Selected Papers from ALENEX 2008

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: 3 - Special Issue

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