ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 17, 2012



Section: SECTION: 1 - Regular Papers

Anatree: A Fast Data Structure for Anagrams
Charles Reams
Article No.: 1.1
DOI: 10.1145/2133803.2133804
Natural language is a rich source of constraint satisfaction problems (CSPs), with a uniquely structured solution domain. We describe a number of approaches to satisfying the particular case of unordered letter-level constraints, including anagrams,...

Route planning with flexible edge restrictions
Robert Geisberger, Michael N. Rice, Peter Sanders, Vassilis J. Tsotras
Article No.: 1.2
DOI: 10.1145/2133803.2133805

In this work, we explore a new type of flexible shortest-path query, in which the query can be dynamically parameterized to constrain the type of edges that may be included in the resulting shortest path (e.g., find the shortest path in a road...

A heuristic for bottleneck crossing minimization and its performance on general crossing minimization: Hypothesis and experimental study
Matthias F. Stallmann
Article No.: 1.3
DOI: 10.1145/2133803.2212314

Extensive research over the last 20 or more years has been devoted to the problem of minimizing the total number of crossings in layered directed acyclic graphs (dags). Algorithms for this problem are used for graph drawing, to implement one of...

Efficient relaxed search in hierarchically clustered sequence datasets
Kai C. Bader, Mikhail J. Atallah, Christian Grothoff
Article No.: 1.4
DOI: 10.1145/2133803.2212315

This article presents a new algorithm for finding oligonucleotide signatures that are specific and sensitive for organisms or groups of organisms in large-scale sequence datasets. We assume that the organisms have been organized in a hierarchy,...

Assignment-minimum clique coverings
John M. Ennis, Charles M. Fayle, Daniel M. Ennis
Article No.: 1.5
DOI: 10.1145/2133803.2275596

The search for minimum clique coverings of graphs appears in many practical guises and with several possible minimization goals. One reasonable goal is to minimize the number of overall cliques in a covering, while a second less well-studied but...

Engineering highway hierarchies
Peter Sanders, Dominik Schultes
Article No.: 1.6
DOI: 10.1145/2133803.2330080

Highway hierarchies exploit hierarchical properties inherent in real-world road networks to allow fast and exact point-to-point shortest-path queries. A fast preprocessing routine iteratively performs two steps: First, it removes edges that only...

Grid sifting: Leveling and crossing reduction
Christian Bachmaier, Wolfgang Brunner, Andreas Gleißner
Article No.: 1.7
DOI: 10.1145/2133803.2345682

Directed graphs are commonly drawn by the Sugiyama algorithm where first vertices are placed on distinct hierarchical levels, and second vertices on the same level are permuted to reduce the overall number of crossings. Separating these two phases...

Section: SECTION: 1 - Regular Papers

Introduction to special issue ALENEX'10
Guy Blelloch, Dan Halperin
Article No.: 2.1
DOI: 10.1145/2133803.2184447

Fast local search for the steiner problem in graphs
Eduardo Uchoa, Renato F. Werneck
Article No.: 2.2
DOI: 10.1145/2133803.2184448

We present efficient algorithms that implement four local searches for the Steiner problem in graphs: vertex insertion, vertex elimination, key-path exchange, and key-vertex elimination. In each case, we show how to find an improving solution (or...

Exact solutions and bounds for general art gallery problems
Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete, Christiane Schmidt
Article No.: 2.3
DOI: 10.1145/2133803.2184449

The classical Art Gallery Problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases. For the case of vertex guards...

StreamKM++: A clustering algorithm for data streams
Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, Christian Sohler
Article No.: 2.4
DOI: 10.1145/2133803.2184450

We develop a new <it>k</it>-means clustering algorithm for data streams of points from a Euclidean space. We call this algorithm StreamKM++. Our algorithm computes a small weighted sample of the data stream and solves the problem on...

Section: SECTION: 1 - Regular Papers

Introduction to special issue ALENEX'11
Matthias Müller-Hannemann, Renato Werneck
Article No.: 3.1
DOI: 10.1145/2133803.2330082

A topological sorting algorithm for large graphs
Deepak Ajwani, Adan Cosgaya-Lozano, Norbert Zeh
Article No.: 3.2
DOI: 10.1145/2133803.2330083

We present an I/O-efficient algorithm for topologically sorting directed acyclic graphs, called IterTS. In the worst case, our algorithm is extremely inefficient and performs O(n ċ sort(m)) I/Os. However, our experiments show...

An SDP approach to multi-level crossing minimization
Markus Chimani, Philipp Hungerländer, Michael Jünger, Petra Mutzel
Article No.: 3.3
DOI: 10.1145/2133803.2330084

We present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization problem. We are given a layered graph (i.e., the graph's vertices are assigned to multiple parallel levels) and are asked for an ordering...

Exact pattern matching with feed-forward bloom filters
Iulian Moraru, David G. Andersen
Article No.: 3.4
DOI: 10.1145/2133803.2330085

This article presents a new, memory efficient and cache-optimized algorithm for simultaneously searching for a large number of patterns in a very large corpus. This algorithm builds upon the Rabin-Karp string search algorithm and incorporates a...

Constructing and sampling graphs with a prescribed joint degree distribution
Isabelle Stanton, Ali Pinar
Article No.: 3.5
DOI: 10.1145/2133803.2330086

One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work...

Section: SECTION: 1 - Regular Papers

ACM journal on experimental algorithmics special issue on multicore algorithms
David A. Bader, Philippas Tsigas
Article No.: 4.1
DOI: 10.1145/2133803.2345675

The recent switch to multicore processors brought a dramatic change that affects a large spectrum of systems from embedded and general-purpose to high-end computing systems. Parallelism is forcing major changes in software development. The aim of...

Fast <it>k</it>-selection algorithms for graphics processing units
Tolu Alabi, Jeffrey D. Blanchard, Bradley Gordon, Russel Steinbach
Article No.: 4.2
DOI: 10.1145/2133803.2345676

Finding the <it>k</it>th-largest value in a list of <it>n</it> values is a well-studied problem for which many algorithms have been proposed. A naïve approach is to sort the list and then simply select the...

An experimental evaluation of the scalability of real-time scheduling algorithms on large-scale multicore platforms
Matthew Dellinger, Aaron Lindsay, Binoy Ravindran
Article No.: 4.3
DOI: 10.1145/2133803.2345677

We present an experimental analysis of the scalability of 13 multicore real-time scheduling algorithms on a 48-core AMD platform. The algorithms include G-EDF, P-EDF, C-EDF, and G-NP-EDF. Comparisons are made based on schedulability and tardiness....

Parallel computation of best connections in public transportation networks
Daniel Delling, Bastian Katz, Thomas Pajor
Article No.: 4.4
DOI: 10.1145/2133803.2345678

Exploiting parallelism in route planning algorithms is a challenging algorithmic problem with obvious applications in mobile navigation and timetable information systems. In this work, we present a novel algorithm for the one-to-all...

Discrete range searching primitive for the GPU and its applications
Jyothish Soman, Kishore Kothapalli, P. J. Narayanan
Article No.: 4.5
DOI: 10.1145/2133803.2345679

Graphics processing units (GPUs) provide large computational power at a very low price, which position GPUs well as an ubiquitous accelerator. However, GPUs are space constrained, and hence applications developed for GPUs are space sensitive.

...