Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 5, 2000

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
Stefan A. Kubricht, Li Xiao, Xiaodong Zhang
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
Igor L. Markov, Andrew E. Caldwell, Andrew B. Kahng
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
Arlindo da Conceicão, João Setubal, Renato Werneck
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
Eti Ezra, Eyal Flato, Iddo Hanniel, Oren Nechushtan, Dan Halperin
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
Jyrki Katajainen, Maz Spork, Jesper Bojesen
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)
H. P. Lenhof, N. P. Boghossian, O. Kohlbacher
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
Andreas Crauser, Klaus Brengel, Ulrich Meyer, Paolo Ferragina
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...