Time Dependent Contraction Hierarchies -- Basic Algorithmic Ideas (2008)
Contraction hierarchies are a simple hierarchical routing technique that has proved extremely efficient for static road networks. We explain how to generalize them to networks with time-dependent...
Polynomial time algorithms for multicast network code construction (2005)
Jaggi, Sidharth, Sanders, Peter, Chou, Philip A., Effros, Michelle, Egner, Sebastian, Jain, Kamal, ...
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has...
Super Scalar Sample Sort (2004)
Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We...
Multi-Platform Benchmarking of the MPI Communications (2004)
Ralf Reussner, Peter Sanders, Jesper Larsson Traff
assing compared to collective MPIAlltoall primitive). Such information allows the application programmer to tune his application for a specific platform bychoosing the appropriate communication...
Engineering a Sorted List Data Structure for (2004)
Roman Dementiev, Lutz Kettner, Jens Mehnert, Peter Sanders
Search tree data structures like van Emde Boas (vEB) trees are a theoretically attractive alternative to comparison based search trees because they have better asymptotic performance for small...
Engineering a Sorted List Data Structure for 32 Bit Keys (2004)
Roman Dementiev, Lutz Kettner, Jens Mehnert, Peter Sanders
Search tree data structures like van Emde Boas (vEB) trees are a theoretically attractive alternative to comparison based search trees because they have better asymptotic performance for small...
Super Scalar Sample Sort (2004)
Sanders, Peter, Albers, Susanne, Radzik, Tomasz
Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Online scheduling with bounded migration (2004)
Sanders, Peter, Sivadasan, Naveen, Skutella, Martin, Díaz, Josep, Karhumäki, Juhani, Lepistö, Arto, ...
Engineering an External Memory Minimum Spanning Tree Algorithm (2004)
Dementiev, Roman, Sanders, Peter, Schultes, Dominik, Sibeyn, Jop F., Lévy, Jean-Jacques, Mayr, Ernst W., ...
We develop an external memory algorithm for computing minimum spanning trees. The algorithm is considerably simpler than previously known external memory algorithms for this problem and needs a...
Engineering a Sorted List Data Structure for 32 Bit Key (2004)
Dementiev, Roman, Kettner, Lutz, Mehnert, Jens, Sanders, Peter, Arge, Lars, Italiano, Giuseppe F., ...
Search tree data structures like van Emde Boas trees are a theoretically attractive alternative to comparison based search trees because they have better asymptotic performance for small integer keys...
Algorithms for Scalable Storage Servers (2004)
Sanders, Peter, Van Emde Boas, Peter, Pokorný, Jaroslav, Bieliková, Mária, Stuller, Július
We survey a set of algorithmic techniques that make it possible to build a high performance storage server from a network of cheap components. Such a storage server offers a very simple programming...
Polynomial Time Algorithms for (2003)
Peter Sanders, Sebastian Egner, Ludo Tolhuizen
The famous max-flow min-cut theorem states that a source node s can send information through a network (V; E) to a sink node t at a rate determined by the min-cut separating s and t. Recently it has...
Algorithms for Scalable Storage Servers (2003)
We survey a set of algorithmic techniques that make it possible to build a high performance storage server from a network of cheap components. Such a storage server oers a very simple programming...
Polynomial Time Algorithms for Multicast Network Code Construction (2003)
Sidharth Jaggi, Peter Sanders, Philip A. Chou, Sebastian Egner, Kamal Jain, Ludo Tolhuizen
The famous max-ow min-cut theorem states that a source node s can send information through a network (V; E) to a sink node t at a rate determined by the min-cut separating s and t. Recently it has...
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property (2003)
We present a simple new (randomized) algorithm for computing minimum spanning trees that is more than two times faster than the best previously known algorithms (for dense, "difficult" inputs). It is...
Asynchronous Parallel Disk Sorting (2003)
Roman Dementiev, Peter Sanders
We develop an algorithm for parallel disk sorting, whose I/O cost approaches the lower bound and that guarantees almost perfect overlap between I/O and computation. Previous algorithms have either...
Asynchronous Scheduling of Redundant Disk Arrays (2003)
Allocation of data to parallel disk using redundant storage and random placement of blocks can be exploited to achieve low access delays. New algorithms are proposed which improve the previously...
Space Efficient Hash Tables With Worst Case Constant Access Time (2003)
Dimitris Fotakis, Rasmus Pagh, Peter Sanders
We generalize Cuckoo Hashing [23] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ffl) n memory cells, for any constant ffl ? 0....
Polynomial Time Algorithms for Network Information Flow (2003)
Peter Sanders, Sebastian Egner, Prof Holstlaan, Ludo Tolhuizen
The famous max-flow min-cut theorem states that a source node s can send information through a network (V; E) to a sink node t at a data rate determined by the min-cut separating s and t. Recently it...
Asynchronous Parallel Disk Sorting (2003)
Roman Dementiev, Peter Sanders
We develop an algorithm for parallel disk sorting, whose I/O cost approaches the lower bound and that guarantees almost perfect overlap between I/O and computation. Previous algorithms have either...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Di Battista, Giuseppe, Zwick, Uri
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
Simple Linear Work Suffix Array Construction (2003)
Kärkkäinen, Juha, Sanders, Peter, Baeten, Jos C.M., Lenstra, Jan Karel, Parrow, Joachim, Woeginger, Gerhard J.
A suffix array represents the suffixes of a string in sorted order. Being a simpler and more compact alternative to suffix trees, it is an important tool for full text indexing and other string...
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul G., Alt, Helmut, Habib, Michel
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property (2003)
Katriel, Irit, Sanders, Peter, Träff, Jesper Larsson, Di Battista, Giuseppe, Zwick, Uri
Scheduling and Traffic Allocation for Tasks with Bounded Splittability (2003)
Krysta, Piotr, Sanders, Peter, Vöcking, Berthold, Rovan, Branislav, Vojtáš, Peter
Full-Text Indexes in External Memory (2003)
Kärkkäinen, Juha, Rao, S. Srinivasa, Meyer, Ulrich, Sanders, Peter, Sibeyn, Jop
Elementary Graph Algorithms in External Memory (2003)
Katriel, Irit, Meyer, Ulrich, Meyer, Ulrich, Sanders, Peter, Sibeyn, Jop
Polynomial Time Algorithms For Network Information Flow (2002)
Peter Sanders, Sebastian Egner, Ludo Tolhuizen
The min-cut in a network defines an upper bound for the (data) rate achievable by a multicast connection. Recently it has been shown that this bound can be achieved if the nodes are allowed to use...
The Hierarchical Factor Algorithm for All-to-all Communication (2002)
Peter Sanders, Jesper Larsson Traff
We present an algorithm for all-to-all personalized communication, in which every processor has an individual message to deliver to every other processor. The machine model we consider is a cluster...
A Lecture on Cuckoo Hashing (2002)
has been intensive research into finding perfect hash functions. The idea is to start with a pseudo-random hash function and than to patch it based on the particular set of elements stored so that it...
Reconciling simplicity and realism in parallel disk models (2002)
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a...
The factor algorithm for regular all-to-all communication on clusters of SMP nodes (2002)
Sanders, Peter, Träff, Jesper Larsson, Monien, Burkhard, Feldman, Rainer
Random Arc Allocation and Applications to Disks, Drums and DRAMs (2002)
Sanders, Peter, Vöcking, Berthold, Penttonen, Martti, Meineche Schmidt, Erik
Energy Optimal Routing in Radio Networks Using Geometric Data Structures (2002)
Beier, Rene, Sanders, Peter, Sivadasan, Naveen, Widmayer, Peter, Triguero, Francisco, Morales, Rafael, ...
Algorithm Engineering for Parallel Computation (2002)
Bader, David, Moret, Bernard, Sanders, Peter, Fleischer, Rudolf, Moret, Bernard, Meineche Schmidt, Erik
The emerging discipline of algorithm engineering has primarily focussed on transforming pencil-and-paper sequential algorithms into robust, efficient, well tested, and easily used implementations. As...
Using Finite Experiments to Study Asymptotic Performance (2002)
McGeoch, Catherine, Sanders, Peter, Fleischer, Rudolf, Cohen, Paul R., Precup, Doina, Fleischer, Rudolf, ...
Presenting Data from Experiments in Algorithmics (2002)
Sanders, Peter, Fleischer, Rudolf, Moret, Bernard, Meineche Schmidt, Erik
Algorithmic experiments yield large amounts of data that depends on many parameters. This paper collects a number of rules for presenting this data in concise, meaningful, understandable graphs that...
Towards Optimal Locality in Mesh-Indexings (2001)
Rolf Niedermeier, Klaus Reinhardt, Peter Sanders
The efficiency of many data structures and algorithms relies on "locality-preserving" indexing schemes for meshes. We concentrate on the case in which the maximal distance between two mesh nodes...
Duality Between Prefetching and Queued Writing with Parallel Disks (2001)
David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat...
Duality Between Prefetching and Queued Writing with Parallel Disks (2001)
David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat...
Multi-Platform Benchmarking of the MPI Communications Interface (2001)
Ralf Reussner, Peter Sanders, Jesper Larsson Traff
s of different realizations of collective operations (eg. alltoall communication via message passing compared to collective MPIAlltoall primitive). Such information allows the application programmer...
Asymptotic Complexity from Experiments? - A Case Study for Randomized Algorithms (2001)
Peter Sanders, Rudolf Fleischer, Max Planck, Insitut Informatik
In the analysis of algorithms we are usually interested in obtaining closed form expressions for their complexity, or at least asymptotic expressions in O(Delta)-notation. Unfortunately, there are...
Presenting Data from Experiments in Algorithmics (2001)
Peter Sanders, Max Planck, Insitut Informatik
Experimental algorithmics yields large amounts of data that depends on many parameters. This paper collects a number of rules for presenting this data in concise, meaningful, understandable diagrams...
How Helpers Hasten h-Relations (2001)
Peter Sanders, Max Planck, Insitut Informatik, Roberto Solis-oba
We study the problem of exchanging a set of messages among a group of processors, where messages may consist of different numbers of packets. We consider the model of half-duplex communication. Let h...
David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat...
The Power of Duality for Prefetching and Sorting with Parallel Disks (2001)
David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
this paper we consider parallel disk input and output separately, in particular as the prefetch scheduling problem and the output scheduling problem, respectively
How Helpers Hasten h-Relations (2001)
Peter Sanders, Max Planck, Insitut Informatik, Roberto Solis-oba
We study the problem of exchanging a set of messages among a group of processors, where messages may consist of different numbers of packets. We consider the model of half-duplex communication. Let h...
Reconciling Simplicity and Realism in Parallel Disk Models (2000)
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a...
Fast Priority Queues for Cached Memory (2000)
This paper advocates the adaption of external memory algorithms to this purpose. This idea and the practical issues involved are exemplified by engineering a fast priority queue suited to external...
How Helpers Hasten h-Relations (2000)
Peter Sanders, Max Planck, Insitut Informatik, Roberto Solis-oba
We study the problem of exchanging a set of messages among a group of processors using the model of simplex communication. Each processor has a unidirectional connection into a fast network. Messages...
Asynchronous Scheduling of Redundant Disk Arrays (2000)
Random redundant allocation of data to parallel disk arrays can be exploited to achieve low access delays. New algorithms are proposed which improve the previously known shortest queue algorithm by...
Fast Concurrent Access to Parallel Disks (2000)
Peter Sanders, Sebastian Egner, Jan Korst
High performance applications involving large data sets require the efficient and flexible use of multiple disks. In an external memory machine with D parallel, independent disks, only one block can...
Scanning Multiple Sequences Via Cache Memory (2000)
We consider the simple problem of scanning multiple sequences. There are k sequences of total length N which are to be scanned concurrently. One pointer into each sequence is maintained and an...
High Performance Integer Optimization for Crew Scheduling (2000)
Peter Sanders, Tuomo Takkula, Dag Wedelin
Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew...
Asynchronous Random Polling Dynamic Load Balancing (1999)
Many applications in parallel processing have to traverse large, implicitly defined trees with irregular shape. The receiver initiated load balancing algorithm random polling has long been known to...
Fast Concurrent Access to Parallel Disks (1999)
Peter Sanders, Sebastian Egner, Jan Korst
High performance applications involving large data sets require the efficient and flexible use of multiple disks. In an external memory machine with D parallel, independent disks, only one block can...
Accessing Multiple Sequences Through Set Associative Caches (1999)
The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms which perform well in practice. We start from the empirical observation...
Parallelizing NP-Complete Problems Using Tree Shaped Computations (1999)
We explain how the parallelization aspects of a large class of applications can be modeled as tree shaped computations. This model is particularly suited for NP-complete problems. One reason for this...
High Performance Integer Optimization for Crew Scheduling (1999)
Peter Sanders, Tuomo Takkula, Dag Wedelin
. Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew...
Fast Priority Queues for Cached Memory (1999)
The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms which perform well in practice. We advocates the approach to adapt...
SKaMPI: A Detailed, Accurate MPI Benchmark (1998)
Ralf Reussner, Peter Sanders, Matthias Muller
SKaMPI is a benchmark for MPI implementations. Its purpose is detailed analysis of the runtime of individual MPI operations and comparison of these for different implementations of MPI. SKaMPI can be...
SKaMPI: A Detailed, Accurate MPI Benchmark (1998)
Ralf Reussner, Peter Sanders, Lutz Prechelt, Matthias Muller
. SKaMPI is a benchmark for MPI implementations. Its purpose is the detailed analysis of the runtime of individual MPI operations and comparison of these for different implementations of MPI. SKaMPI...
An Implementation of the Binary Blocking Flow Algorithm (1998)
Torben Hagerup, Peter Sanders, Jesper Larsson Traff
Goldberg and Rao recently devised a new binary blocking flow algorithm for computing maximum flows in networks with integer capacities. We describe an implementation of variants of the binary...
Tree Shaped Computations as a Model for Parallel Applications (1998)
It is shown how a large class of applications can be parallelized by modeling them as tree shaped computations. In particular this class contains many highly irregular and completely unpredictable...
Randomized Receiver Initiated Load Balancing Algorithms for Tree Shaped Computations (1998)
Many applications in parallel processing have to traverse large, implicitly defined trees with irregular shape. The receiver initiated load balancing algorithm asynchronous random polling has long...
Towards Optimal Locality in Mesh-Indexings (1997)
Rolf Niedermeier, Klaus Reinhardt, Peter Sanders
The efficiency of many data structures and algorithms relies on "locality-preserving" indexing schemes for meshes. We concentrate on the case where the maximal distance between two mesh nodes indexed...
Better Algorithms for Parallel Backtracking (1997)
Many algorithms in operations research and artificial intelligence are based on the backtracking principle, i.e., depth first search in implicitly defined trees. For parallelizing these algorithms,...