enter search term and/or author name
Anatree: A Fast Data Structure for Anagrams
Article No.: 1.1
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,...
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
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
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,...
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...
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...
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...
Fast local search for the steiner problem in graphs
Eduardo Uchoa, Renato F. Werneck
Article No.: 2.2
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
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
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...
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
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
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
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
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
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
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
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
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....