enter search term and/or author name
Fast hierarchical clustering and other applications of dynamic closest pairs
Article No.: 1
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
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
Stefan A. Kubricht, Li Xiao, Xiaodong Zhang
Article No.: 3
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
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
Igor L. Markov, Andrew E. Caldwell, Andrew B. Kahng
Article No.: 5
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
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
Article No.: 7
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
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
Article No.: 9
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
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
Arlindo da Conceicão, João Setubal, Renato Werneck
Article No.: 11
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
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
Eti Ezra, Eyal Flato, Iddo Hanniel, Oren Nechushtan, Dan Halperin
Article No.: 13
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
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
Jyrki Katajainen, Maz Spork, Jesper Bojesen
Article No.: 15
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 , in which elements are repeatedly inserted into a single heap;...
Rapid software prototyping in molecular modeling using the biochemical algorithms library (BALL)
H. P. Lenhof, N. P. Boghossian, O. Kohlbacher
Article No.: 16
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
Andreas Crauser, Klaus Brengel, Ulrich Meyer, Paolo Ferragina
Article No.: 17
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...