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