enter search term and/or author name
An experimental study of recent hotlink assignment algorithms
Article No.: 1.1
The concept of hotlink assignment aims at enhancing the structure of Web sites such that the user's expected navigation effort is minimized. We concentrate on sites that are representable by trees and assume that each leaf carries a weight...
sgen1: A generator of small but difficult satisfiability benchmarks
Article No.: 1.2
The satisfiability problem is known to be NP-Complete; therefore, there should be relatively small problem instances that take a very long time to solve. However, most of the smaller benchmarks that were once thought challenging, especially the...
Heuristic initialization for bipartite matching problems
Johannes Langguth, Fredrik Manne, Peter Sanders
Article No.: 1.3
It is a well-established result that improved pivoting in linear solvers can be achieved by computing a bipartite matching between matrix entries and positions on the main diagonal. With the availability of increasingly faster linear solvers, the...
Analytical and experimental comparison of six algorithms for the vertex cover problem
François Delbot, Christian Laforest
Article No.: 1.4
The vertex cover is a well-known NP-complete minimization problem in graphs that has received a lot of attention these last decades. Many algorithms have been proposed to construct vertex cover in different contexts (offline, online, list...
Practical approaches to reduce the space requirement of lempel-ziv--based compressed text indices
Diego Arroyuelo, Gonzalo Navarro
Article No.: 1.5
Given a text T[1¨n] over an alphabet of size σ, the full-text search problem consists in locating the occ occurrences of a given pattern P[1¨m] in T. Compressed full-text...
Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
Julian R. Ullmann
Article No.: 1.6
A solution to a binary constraint satisfaction problem is a set of discrete values, one in each of a given set of domains, subject to constraints that allow only prescribed pairs of values in specified pairs of domains. Solutions are sought by...
Redesigning the string hash table, burst trie, and BST to exploit cache
Nikolas Askitis, Justin Zobel
Article No.: 1.7
A key decision when developing in-memory computing applications is choice of a mechanism to store and retrieve strings. The most efficient current data structures for this task are the hash table with move-to-front chains and the burst trie, both...
An upward drawing of a DAG G is a drawing of G in which all arcs are drawn as curves increasing monotonically in the vertical direction. In this article, we present a new approach for upward crossing minimization, that is, finding an...
Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, Dorothea Wagner
Article No.: 2.3
In recent years, highly effective hierarchical and goal-directed speed-up techniques for routing in large road networks have been developed. This article makes a systematic study of combinations of such techniques. These combinations turn out to...
Comparing integer data structures for 32- and 64-bit keys
Nicholas Nash, David Gregg
Article No.: 2.4
In this article, we experimentally compare a number of data structures operating over keys that are 32- and 64-bit integers. We examine traditional comparison-based search trees as well as data structures that take advantage of the fact that the...
Engineering burstsort: Toward fast in-place string sorting
Ranjan Sinha, Anthony Wirth
Article No.: 2.5
Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. This approach has earlier been demonstrated to be efficient on modern cache-based processors [Sinha & Zobel,...