ACM Journal of Experimental Algorithmics

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 x₀ of the vertices on a layer, find a perumuation x₁ of the vertices on the other layer which minimizes the number of edge crossings in any ...

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 the hospital, ...

We present an experimental study of different variants of the amortized O(log² n)-time fully-dynamic connectivity algorithm of Holm, de Lichtenberg, and Thorup (STOC'98). The experiments build upon experiments provided by Alberts, Cattaneo, and Italiano (...

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 number ...

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 L_p or polyhedral metric. A theoretical analysis shows that it has an expected running time of O(n ...

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 make ...

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 two ...

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 propose ...

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 of most popular ...