enter search term and/or author name
Generating node coordinates for shortest-path computations in transportation networks
Frank Schulz, Dorothea Wagner, Thomas Willhalm, Ulrik Brandes
Article No.: 1.1
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
José Nelson Amaral, Robert Niewiadomski, Robert C. Holte
Article No.: 1.2
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
Larry D. Risinger, jr, Alessandro Panconesi, Madhav V. Marathe
Article No.: 1.3
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
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
Justin Zobel, Ranjan Sinha
Article No.: 1.5
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
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...