Search ACM DL

Search Issue

enter search term and/or author name

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

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

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

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

...