ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 3, 1998

Power balance and apportionment algorithms for the United States Congress
Lane A. Hemaspaandra, Kulathur S. Rajasethupathy, Prasanna Sethupathy, Marius Zimand
Article No.: 1
DOI: 10.1145/297096.297106
We measure the performance, in the task of apportioning the Congress of the United States, of an algorithm combining a heuristic-driven (simulated annealing) search with an exact-computation dynamic programming evaluation of the apportionments...

Weight-biased leftist trees and modified skip lists
Seonghun Cho, Sartaj Sahni
Article No.: 2
DOI: 10.1145/297096.297111
We propose the weight biased leftist tree as an alternative to traditional leftist trees [CRAN72] for the representation of mergeable priority queues. A modified version of skip lists [PUGH90] that uses fixed size nodes is also proposed. Experimental...

Lock bypassing: an efficient algorithm for concurrently accessing priority heaps
Yong Yan, Xiaodong Zhang
Article No.: 3
DOI: 10.1145/297096.297116
The heap representation of priority queues is one of the most widely used data structures in the design of parallel algorithms. Efficiently exploiting the parallelism of a priority heap has significant influence on the efficiency of a wide range of...

A new deterministic parallel sorting algorithm with an experimental evaluation
David R. Helman, Joseph JáJá, David A. Bader
Article No.: 4
DOI: 10.1145/297096.297128
We introduce a new deterministic parallel sorting algorithm for distributed memory machines based on the regular sampling approach. The algorithm uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good...

Experimental analysis of dynamic algorithms for the single source shortest paths problem
Daniele Frigioni, Mario Ioffreda, Umberto Nanni, Giulio Pasqualone
Article No.: 5
DOI: 10.1145/297096.297147
In this paper we propose the first experimental study of the fully dynamic single-source shortest-paths problem on directed graphs with positive real edge weights. In particular, we perform an experimental analysis of three different algorithms:...

Greeding matching algorithms, an experimental study
Jakob Magun
Article No.: 6
DOI: 10.1145/297096.297131
We conduct an experimental study of several greedy algorithms for finding large matchings in graphs. Further we propose a new graph reduction, called <i>k</i>-Block Reduction, and present two novel algorithms using extra heuristics in the...

Implementing radixsort
Arne Andersson, Stefan Nilsson
Article No.: 7
DOI: 10.1145/297096.297136
We present and evaluate several optimization and implementation techniques for string sorting. In particular, we study a recently published radix sorting algorithm, Forward radixsort, that has a provably good worst-case behavior. Our experimental...

Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms
Boris V. Cherkassky, Andrew V. Goldberg, Paul Martin, Joao C. Setubal, Jorge Stolfi
Article No.: 8
DOI: 10.1145/297096.297140
We conduct a computational study of unit capacity flow and bipartite matching algorithms. Our goal is to determine which variant of the push-relabel method is most efficient in practice and to compare push-relabel algorithms with augmenting path...

Implementation of dynamic trees with in-subtree operations
Tomasz Radzik
Article No.: 9
DOI: 10.1145/297096.297144
We describe an implementation of dynamic trees with "in-subtree" operations. Our implementation follows Sleator and Tarjan's framework of dynamic-tree implementations based on splay trees. We consider the following two examples of "in-subtree"...