enter search term and/or author name
Power balance and apportionment algorithms for the United States Congress
Lane A. Hemaspaandra, Kulathur S. Rajasethupathy, Prasanna Sethupathy, Marius Zimand
Article No.: 1
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
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
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
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
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
Article No.: 6
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...
Arne Andersson, Stefan Nilsson
Article No.: 7
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
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
Article No.: 9
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"...