enter search term and/or author name
I/O-Efficient Algorithms for Problems on Grid-Based Terrains
Lars Arge, Laura Toma, Jeffrey Scott Vitter
Article No.: 1
The potential and use of Geographic Information Systems is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to Planet Earth. However, the use of these massive datasets also...
We consider the one-sided crossing minimization problem (CP): given a bipartite graph G and a permutation x0 of the vertices on a layer, find a perumuation x1 of the vertices on the other layer which ...
A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis
Harold Gabow, Tadayoshi Kohno
Article No.: 3
We describe a program that schedules physician attending teams at Denver Health Medical Center. The program uses network flow techniques to prune an exponentially sized search space. We describe the program design, its performance history at...
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
Raj Iyer, David Karger, Hariharan Rahul, Mikkel Thorup
Article No.: 4
We present an experimental study of different variants of the amortized O(log2 n)-time fully-dynamic connectivity algorithm of Holm, de Lichtenberg, and Thorup (STOC'98). The experiments build upon experiments provided...
Caching and Scheduling for Broadcast Disk Systems
Article No.: 5
Unicast connections lead to performance and scalability problems when a large client population attempts to access the same data. Broadcast push and broadcast disk technology address the problem by broadcasting data items from a server to a large...
Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions
Giri Narasimhan, Martin Zachariasen
Article No.: 6
Let S be a set of n points in ℜd. We present an algorithm that uses the well-separated pair decomposition and computes the minimum spanning tree of S under any Lp or polyhedral ...
Adapting Radix Sort to the Memory Hierarchy
Naila Rahman, Rajeev Raman
Article No.: 7
We demonstrate the importance of reducing misses in the translation-lookaside buffer (TLB) for obtaining good performance on modern computer architectures. We focus on least-significantbit first (LSB) radix sort, standard implementations of which...
Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization
Matthias Stallmann, Franc Brglez, Debabrata Ghosh
Article No.: 8
The bigraph crossing problem, embedding the two node sets of a bipartite graph along two parallel lines so that edge crossings are minimized, has applications to circuit layout and graph drawing. Experimental results for several previously known and...
An Experimental Study of Dynamic Algorithms for Transitive Closure
Daniele Frigioni, Tobias Miller, Umberto Nanni, Christos Zaroliagis
Article No.: 9
We perform an extensive experimental study of several dynamic algorithms for transitive closure. In particular, we implemented algorithms given by Italiano, Yellin, Cicerone et al., and two recent randomized algorithms by Henzinger and King. We...
The Effect of Flexible Parsing for Dynamic Dictionary-Based Data Compression
Yossi Matias, Nasir Rajpoot, Cenk Sahinalp
Article No.: 10
We report on the performance evaluation of greedy parsing with a single step lookahead (which we call flexible Parsing or FP as an alternative to the commonly used greedy parsing (with no-lookaheads) scheme. Greedy parsing is the basis...