Search ACM DL

Search Issue

enter search term and/or author name

**An experimental study of recent hotlink assignment algorithms**

Tobias Jacobs

Article No.: 1.1

DOI: 10.1145/1671970.1671971

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

Ivor Spence

Article No.: 1.2

DOI: 10.1145/1671970.1671972

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

DOI: 10.1145/1671970.1712656

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

DOI: 10.1145/1865970.1865971

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

DOI: 10.1145/1671970.1883684

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
DOI: 10.1145/1671970.1921702
*

*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
DOI: 10.1145/1671970.1921704
*

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

**Preface**

Catherine C. McGeoch

Article No.: 2.1

DOI: 10.1145/1671970.1671974

**Layer-free upward crossing minimization**

Markus Chimani, Carsten Gutwenger, Petra Mutzel, Hoi-Ming Wong

Article No.: 2.2

DOI: 10.1145/1671970.1671975

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

DOI: 10.1145/1671970.1671976

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

DOI: 10.1145/1671970.1671977

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

DOI: 10.1145/1671970.1671978

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