ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 9, 2004

Section: 1 - Regular Articles

Generating node coordinates for shortest-path computations in transportation networks
Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Article No.: 1.1
DOI: 10.1145/1005813.1005815
Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such techniques when coordinates are missing from some,...

A performance study of data layout techniques for improving data locality in refinement-based pathfinding
Robert Niewiadomski, José Nelson Amaral, Robert C. Holte
Article No.: 1.2
DOI: 10.1145/1005813.1041511
The widening gap between processor speed and memory latency increases the importance of crafting data structures and algorithms to exploit temporal and spatial locality. Refinement-based pathfinding algorithms, such as Classic Refinement (CR), find...

An experimental study of a simple, distributed edge-coloring algorithm
Madhav V. Marathe, Alessandro Panconesi, Larry D. Risinger, jr
Article No.: 1.3
DOI: 10.1145/1005813.1041515
We conduct an experimental analysis of a distributed randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly...

Average-optimal single and multiple approximate string matching
Kimmo Fredriksson, Gonzalo Navarro
Article No.: 1.4
DOI: 10.1145/1005813.1041513
We present a new algorithm for multiple approximate string matching. It is based on reading backwards enough l-grams from text windows so as to prove that no occurrence can contain the part of the window read, and then shifting the window.We show...

Cache-conscious sorting of large sets of strings with dynamic tries
Ranjan Sinha, Justin Zobel
Article No.: 1.5
DOI: 10.1145/1005813.1041517
Ongoing changes in computer architecture are affecting the efficiency of string-sorting algorithms. The size of main memory in typical computers continues to grow but memory accesses require increasing numbers of instruction cycles, which is a...

Twol-amalgamated priority queues
Rick Siow Mong Goh, Ian Li-Jin Thng
Article No.: 1.6
DOI: 10.1145/1005813.1057625
Priority queues are essential function blocks in numerous applications such as discrete event simulations. This paper describes and exemplifies the ease of obtaining high performance priority queues using a two-tier list-based structure. This new...