Search ACM DL

Search Issue

enter search term and/or author name

**Fast hierarchical clustering and other applications of dynamic closest pairs**

David Eppstein

Article No.: 1

DOI: 10.1145/351827.351829

We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs,...

**Correspondence-based data structures for double-ended priority queues**

Article No.: 2

DOI: 10.1145/351827.351828

We describe three general methods--total, dual, and leaf correspondence--that may be used to derive efficient double-ended priority queues from single-ended priority queues. These methods are illustrated by developing double-ended priority queues...

**Improving memory performance of sorting algorithms**

Li Xiao, Xiaodong Zhang, Stefan A. Kubricht

Article No.: 3

DOI: 10.1145/351827.384245

Memory hierarchy considerations during sorting algorithm design and implementation play an important role in significantly improving execution performance. Existing algorithms mainly attempt to reduce capacity misses on direct-mapped caches. To...

**Fast and flexible string matching by combining bit-parallelism and suffix automata**

Gonzalo Navarro, Mathieu Raffinot

Article No.: 4

DOI: 10.1145/351827.384246

The most important features of a string matching algorithm are its efficiency and its flexibility. Efficiency has traditionally received more attention, while flexibility in the search pattern is becoming a more and more important issue. Most...

**Design and implementation of move-based heuristics for VLSI hypergraph partitioning**

Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov

Article No.: 5

DOI: 10.1145/351827.384247

We summarize the techniques of implementing move-based hypergraph partitioning heuristics and evaluating their performance in the context of VLSI design applications. Our first contribution is a detailed software architecture, consisting of seven...

**Finding the right cutting planes for the TSP**

Matthew S. Levine

Article No.: 6

DOI: 10.1145/351827.384248

Given an instance of the Traveling Salesman Problem (TSP), a reasonable way to get a lower bound on the optimal answer is to solve a linear programming relaxation of an integer programming formulation of the problem. These linear programs typically...

**Fast priority queues for cached memory**

Peter Sanders

Article No.: 7

DOI: 10.1145/351827.384249

The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms that perform well in practice. This paper advocates the adaption of external memory algorithms to this purpose. This idea...

**Implementing weighted b-matching algorithms**: insights from a computational study

Matthias Müller-Hannemann, Alexander Schwartz

Article No.: 8

DOI: 10.1145/351827.384250

We present an experimental study of an implementation of weighted perfect <i>b</i>-matching based on the primal-dual blossom algorithm. Although this problem is well-understood in theory and efficient algorithms are known, only little...

**Computing the nxm shortest path efficiently**

Tetsuo Shibuya

Article No.: 9

DOI: 10.1145/351827.384251

Computation of all the shortest paths between multiple sources and multiple destinations on various networks is required in many problems, such as the traveling salesperson problem (TSP) and the vehicle routing problem (VRP). This paper proposes new...

**Experiments with list ranking for explicit multi-threaded (XMT) instruction parallelism**

Dascal Vishkin, Uzi Vishkin

Article No.: 10

DOI: 10.1145/351827.384252

Algorithms for the problem of list ranking are empirically studied with respect to the Explicit Multi-Threaded (XMT) platform for instruction-level parallelism (ILP). The main goal of this study is to understand the differences between XMT and...

**Finding minimum congestion spanning trees**

Renato Werneck, João Setubal, Arlindo da Conceicão

Article No.: 11

DOI: 10.1145/351827.384253

Given a weighted graph <i>G = (V, E)</i>, a positive integer <i>k</i>, and a penalty function <i>w<inf>p</inf></i>, we want to find <i>k</i> spanning trees on <i>G</i>, not...

**Dijkstra's algorithm on-line**: an empirical case study from public railroad transport

Frank Schulz, Dorothea Wagner, Karsten Weihe

Article No.: 12

DOI: 10.1145/351827.384254

Traffic information systems are among the most prominent real-world applications of Dijkstra's algorithm for shortest paths. We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks....

**The design and implementation of panar maps in CGAL**

Eyal Flato, Dan Halperin, Iddo Hanniel, Oren Nechushtan, Eti Ezra

Article No.: 13

DOI: 10.1145/351827.384255

Planar maps are fundamental structures in computational geometry. They are used to represent the subdivision of the plane into regions and have numerous applications. We describe the planar map package of CGAL--a Computational Geometry Algorithms...

**Analysing cache effects in distribution sorting**

Naila Rahman, Rajeev Raman

Article No.: 14

DOI: 10.1145/351827.384256

We study cache effects in distribution sorting algorithms for sorting keys drawn independently at random from a uniform distribution ('uniform keys'). We note that the performance of a recently-published distribution sorting algorithm, Flashsort1,...

**Performance engineering case study**: heap construction

Jesper Bojesen, Jyrki Katajainen, Maz Spork

Article No.: 15

DOI: 10.1145/351827.384257

The behaviour of three methods for constructing a binary heap on a computer with a hierarchical memory is studied. The methods considered are the original one proposed by Williams [1964], in which elements are repeatedly inserted into a single heap;...

**Rapid software prototyping in molecular modeling using the biochemical algorithms library (BALL)**

N. P. Boghossian, O. Kohlbacher, H. P. Lenhof

Article No.: 16

DOI: 10.1145/351827.384258

In the next century, virtual laboratories will play a key role in biotechnology. Computer experiments will not only replace some of the time-consuming and expensive real-world experiments, but they will also provide insights that cannot be obtained...

**An experimental study of priority queues in external memory**

Klaus Brengel, Andreas Crauser, Paolo Ferragina, Ulrich Meyer

Article No.: 17

DOI: 10.1145/351827.384259

In this paper we compare the performance of eight different priority queue implementations: four of them are explicitly designed to work in an external-memory setting, the others are standard internal-memory queues available in the LEDA library...