Publications of Peter Sanders

Refereed Conference Papers

1
P. Sanders and D. Steurer. An Asymptotic Approximation Scheme for Multigraph Edge Coloring. In 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.

2
R. Dementiev, J. Mehnert, and J. Kärkkäinen. Better External Memory Suffix Array Construction. In Workshop on Algorithm Engineering & Experiments, Vancouver, 2005.

3
P. Sanders and S. Winkel. Super Scalar Sample Sort. In 12th European Symposium on Algorithms (ESA), volume 3221 of LNCS, pages 784-796. Springer ©, 2004.

4
P. Sanders, N. Sivadasan, and M. Skutella. Online Scheduling with Bounded Migration. In 31st International Colloquium on Automata, Languages and Programming (ICALP), number 2719 in LNCS, pages 1111-1122. Springer ©, 2004.

5
P. Sanders. Algorithms for Scalable Storage Servers. In SOFSEM 2004: Theory and Practice of Computer Science, volume 2932 of LNCS, pages 82-101. Springer ©, 2004.

6
R. Dementiev, L. Kettner, J. Mehnert, and P. Sanders. Engineering a Sorted List Data Structure for 32 Bit Keys. In Workshop on Algorithm Engineering & Experiments, pages 142-151, New Orleans, 2004.

7
S. Funke, D. Matijevic, and P. Sanders. Approximating Energy Efficient Paths in Multi-Hop Networks. In 11th European Symposium on Algorithms (ESA), number 2832 in LNCS. Springer, 2003.

8
P. Krysta, P. Sanders, and B. Vöcking. Scheduling and traffic allocation for tasks with bounded splittability. In 28th International Symposium on Mathematical Foundations of Computer Science, number 2747 in LNCS, pages 500-510. Springer, 2003.

9
I. Katriel, P. Sanders, and J. L. Träff. A Practical Minimum Spanning Tree Algorithm Using the Cycle Property. In 11th European Symposium on Algorithms (ESA), number 2832 in LNCS, pages 679-690. Springer, 2003.

10
P. Sanders, S. Egner, and L. Tolhuizen. Polynomial Time Algorithms For Network Information Flow. In 15th ACM Symposium on Parallel Algorithms and Architectures, pages 286-294, 2003.

11
J. Kärkkäinen and P. Sanders. Simple Linear Work Suffix Array Construction. In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS, pages 943-955. Springer ©, 2003.

12
R. Dementiev and P. Sanders. Asynchronous Parallel Disk Sorting. In 15th ACM Symposium on Parallelism in Algorithms and Architectures, pages 138-148, San Diego, 2003.

13
D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis. Space efficient hash tables with worst case constant access timefull paper. In 20th International Symposium on Theoretical Aspects of Computer Science, number 2607 in LNCS, pages 271-282, Berlin, 2003. Springer.

14
Peter Sanders and Jesper Larsson Träff. The factor algorithm for regular all-to-all communication on clusters of SMP nodes. In 8th Europar, number 2400 in LNCS, pages 799-803. Springer ©, 2002. full paper.

15
P. Sanders and B. Vöcking. Random Arc Allocation and Applications to Disks, Drums and DRAMs. In 8th Scandinavian Workshop on Algorithm Theory, number 2368 in LNCS, pages 121-130. Springer ©, 2002. full paper.

16
R. Beier, P. Sanders, and N. Sivadasan. Energy Optimal Routing in Radio Networks Using Geometric Data Structures. In 29th International Colloquium on Automata, Languages and Programming, number 2380 in LNCS, pages 366-376. Springer ©, 2002.

17
D. A. Hutchinson, P. Sanders, and J. S. Vitter. Duality Between Prefetching and Queued Writing with Parallel Disks. In 9th European Symposium on Algorithms (ESA), number 2161 in LNCS, pages 62-73. Springer©, 2001.

18
P. Sanders. Reconciling Simplicity and Realism in Parallel Disk Models. In 12th ACM-SIAM Symposium on Discrete Algorithms, pages 67-76, Washington DC, 2001.

19
P. Sanders and R. Fleischer. Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms. In Workshop on Algorithm Engineering, number 1982 in LNCS, pages 135-146. Springer ©, 2000.

20
P. Sanders and R. Solis-Oba. How Helpers Hasten h-Relations. In 8th European Symposium on Algorithms (ESA), number 1879 in LNCS, pages 392-402, 2000. final paper.

21
U. Meyer and P. Sanders. Parallel Shortest Path for Arbitrary Graphs. In 6th Euro-Par, number 1900 in LNCS, pages 461-470. Springer ©, 2000.

22
P. Sanders and J. Sibeyn. A Bandwidth Latency Tradeoff for Broadcast and Reduction. In 6th Euro-Par, number 1900 in LNCS, pages 918-926. Springer ©, 2000.

23
P. Sanders. Asynchronous Scheduling of Redundant Disk Arrays. In 12th ACM Symposium on Parallel Algorithms and Architectures, pages 89-98, 2000.

24
P. Sanders, S. Egner, and J. Korst. Fast Concurrent Access to Parallel Disks. In 11th ACM-SIAM Symposium on Discrete Algorithms, pages 849-858, 2000. full paper.

25
P. Sanders. Asynchronous Random Polling Dynamic Load Balancing. In ISAAC: 10th International Symposium on Algorithms and Computation, LNCS, pages 37-48, Chennai, India, Dec. 1999. Springer ©. full paper.

26
P. Sanders. Accessing Multiple Sequences Through Set Associative Caches. In ICALP, number 1644 in LNCS, pages 655-664. Springer ©, 1999. extended version (with K. Mehlhorn).

27
P. Sanders, T. Takkula, and D. Wedelin. High Performance Integer Optimization for Crew Scheduling. In 7th International Conference on High Performance Computing and Networking Europe, number 1593 in LNCS, pages 3-12. Springer ©, 1999. full paper.

28
Peter Sanders. Fast Priority Queues for Cached Memory. In ALENEX '99, Workshop on Algorithm Engineering and Experimentation, number 1619 in LNCS, pages 312-327. Springer ©, 1999. Extended version in ACM Journal of Experimental Algorithmics.

29
R. Reussner, P. Sanders, L. Prechelt, and M. Müller. SKaMPI: A Detailed, Accurate MPI Benchmark. In EuroPVM/MPI, number 1497 in LNCS, pages 52-59, 1998. (SKaMPI Home Page).

30
A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. A Parallelization of Dijkstra's Shortest Path Algorithm. In 23rd Symposium on Mathematical Foundations of Computer Science, number 1450 in LNCS, pages 722-731, Brno, Czech Republic, 1998. Springer ©.

31
P. Alefragis, C. Goumopoulos, E. Housos, P. Sanders, T. Takkula, and D. Wedelin. Parallel crew scheduling in PAROS. In 4th Euro-Par, number 1470 in LNCS, pages 1104-1113. Springer ©, 1998.

32
U. Meyer and P. Sanders. -Stepping: A Parallel Shortest Path Algorithm. In 6th European Symposium on Algorithms (ESA), number 1461 in LNCS, pages 393-404. Springer ©, 1998.

33
T. Hagerup, P. Sanders, and J. L. Träff. An Implementation of the Binary Blocking Flow Algorithm. In K. Mehlhorn, editor, 2nd Workshop on Algorithm Engineering, number MPI-I-98-1-019, ISSN: 0946-011X in Research Reports MPII, 1998.

34
P. Sanders. Tree Shaped Computations as a Model for Parallel Applications. In ALV'98 Workshop on application based load balancing, pages 123-132. SFB 342, TU München, Germany, March 1998.

35
R. Niedermeier, K. Reinhard, and P. Sanders. Towards optimal locality in mesh-indexings. In B. S. Chlebus and L. Czaja, editors, Fundamentals of Computation Theory, number 1279 in LNCS, pages 364-375, Krakow, 1997. Extended version as Technical Report IB 12/97, University of Karlsruhe, 1997.

36
Peter Sanders, Roland Vollmar, and Thomas Worsch. Feasible models of computation: Three-dimensionality and energy consumption. In C. Lengauer, M. Griebl, and S. Gorlatch, editors, Euro-Par, number 1300 in LNCS, pages 384-388, Passau, 1997. Springer ©. Extended version as Technical Report IB 2/97, University of Karlsruhe, 1997.

37
P. Sanders and T. Hansch. On the Efficient Implementation of Massively Parallel Quicksort. In 4th International Symposium on Solving Irregularly Structured Problems in Parallel, number 1253 in LNCS, pages 13-24. Springer ©, 1997. Thomas Hansch's Diploma thesis (in German), University of Karlsruhe, 1996. Complete set of data sheets (English translation).

38
P. Sanders. Optimizing the emulation of MIMD behavior on SIMD machines. In Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays, Berlin, 1996. Akademie Verlag. Extended version.

39
P. Sanders. On the efficiency of nearest neighbor load balancing for random loads. In Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays, pages 120-127, Berlin, 1996. Akademie Verlag. Extended version.

40
P. Sanders. On the Competitive Analysis of Randomized Static Load Balancing. In S. Rajasekaran, editor, First Workshop on Randomized Parallel Algorithms, Honolulu, Hawaii, 16 April, 1996.

41
H. Hopp and P. Sanders. Parallel Game Tree Search on SIMD Machines. In Workshop on Algorithms for Irregularly Structured Problems, number 980 in LNCS, pages 349-361, Lyon, 1995. Springer ©. Holger Hopp's Diploma thesis (in German), University of Karlsruhe, 1995.

42
P. Sanders. Fast priority queues for parallel branch-and-bound. In Workshop on Algorithms for Irregularly Structured Problems, number 980 in LNCS, pages 379-393, Lyon, 1995. Springer ©. Improved version in JPDC, extended version.

43
P. Sanders. Better Algorithms for Parallel Backtracking. In Workshop on Algorithms for Irregularly Structured Problems, number 980 in LNCS, pages 333-347, Lyon, 1995. Springer ©. Extended version.

44
P. Sanders. A Detailed Analysis of Random Polling Dynamic Load Balancing. In International Symposium on Parallel Architectures, Algorithms and Networks, pages 382-389, Kanazawa, Japan, 1994.

45
P. Sanders. Massively Parallel Search for Transition-Tables of Polyautomata. In Parcella 94, VI. International Workshop on Parallel Proccessing by Cellular Automata and Array, pages 99-108, Potsdam, 1994.

46
P. Sanders. Emulating MIMD behavior on SIMD machines. In International Conference Massively Parallel Processing Applications and Development, pages 313-321, Delft, 1994. Elsevier.

47
P. Sanders. A Case Study in Object Oriented Programming: Algebraic Data Structures in Eiffel. In R. Ege, M. Singh, and B. Meyer, editors, Technology of Object-Oriented Languages and Systems, number 11 in TOOLS, pages 379-388, Santa Barbara, 1993. Prentice Hall.

Journals

1
S. Pettie and P. Sanders. A simpler linear time approximation
for maximum weight matching. Information Processing Letters, 2004. in press.

2
U. Meyer and P. Sanders. -stepping: A parallelizable shortest path algorithm. Journal of Algorithms, 2003. in press.

3
P. Sanders and B. Vöcking. Tail bounds and expectations for random arc allocation and applications. Combinatorics Probability and Computing, 12(3):301-318, 2003.

4
P. Sanders and J. Sibeyn. A bandwidth latency tradeoff for broadcast and reduction. Information Processing Letters, 86(1):33-38, 2003.

5
P. Sanders. Asynchronous scheduling of redundant disk arrays. IEEE Transactions on Computers, 52(9):1170-1184, 2003.

6
K. Mehlhorn and P. Sanders. Scanning multiple sequences via cache memory. Algorithmica, 35(1):75-93, 2003.

7
Peter Sanders. Randomized receiver initiated load balancing algorithms for tree shaped computations. The Computer Journal, 45(5):561-573, 2002.

8
R. Niedermeier, K. Reinhard, and P. Sanders. Towards optimal locality in mesh-indexings. Discrete Applied Mathematics, 117:211-237, march 2002.

9
P. Sanders, R. Vollmar, and T. Worsch. Feasible models of computation: Three-dimensionality and energy consumption. Fundamenta Informaticae, 52(1-3):233-248, 2002.

10
R. Reussner, P. Sanders, and J. Träff. SKaMPI: A comprehensive benchmark for public benchmarking of MPI. Scientific Programming, 10(1):55-65, 2001.

11
P. Sanders. Reconciling simplicity and realism in parallel disk models. Parallel Computing, 28(5):705-723, 2002. Special Issue on Parallel Data Intensive Algorithms and Applications.

12
P. Sanders and R. Solis-Oba. How helpers hasten h-relations. Journal of Algorithms, 41:86-98, 2001.

13
P. Sanders. Fast Priority Queues for Cached Memory. ACM Journal of ExperimentalAlgorithmics, 5, 2000.

14
P. Alefragis, P. Sanders, T. Takkula, and D. Wedelin. Parallel integer optimization for crew scheduling. Annals of Operations Research, 99(1):141-166, 2000.

15
P. Sanders. Analysis of nearest neighbor load balancing algorithms for random loads. Parallel Computing, 25:1013-1033, 1999.

16
U. Rathe, P. Sanders, and P. Knight. A case study in scalability: an ADI method for the two-dimensional time-dependent Dirac equation. Parallel Computing, 25(5):525-534, may 1999.

17
P. Sanders. Random permutations on distributed, external and hierarchical memory. Information Processing Letters, 67(6):305-310, 1998.

18
P. Sanders. Randomized priority queues for fast parallel access. Journal Parallel and Distributed Computing, Special Issue on Parallel and Distributed Data Structures, 49:86-97, 1998. Extended version.

19
B. Beckert, A. Bell, and P. Sanders. Gedichtgenerator -- Ein Anwendungsbeispiel für natürlichsprachliche Texterzeugung. Junge Wissenschaft, 3(10):28-37, 1988.

Books and Book Chapters

1
U. Meyer, P. Sanders, and J. Sibeyn, editors. Algorithms for Memory Hierarchies, volume 2625 of LNCS Tutorial. Springer, 2003.

2
P. Sanders. Presenting Data from Experiments in Algorithmics. In Experimental Algorithmics -- From Algorithm Design to Robust and Efficient Software, volume 2547 of LNCS, pages 181-196. Springer ©, 2002.

3
C. McGeoch, P. Sanders, R. Fleischer, P. R. Cohen, and D. Precup. Searching for Big-Oh in the Data: Inferring Asymptotic Complexity from Experiments. In Experimental Algorithmics -- From Algorithm Design to Robust and Efficient Software, volume 2547 of LNCS. Springer ©, 2002.

4
D. Bader, B. Moret, and P. Sanders. Algorithm Engineering for Parallel Computation. In Experimental Algorithmics From Algorithm Design to Robust and Efficient Software, volume 2547 of LNCS, pages 1-23. Springer ©, 2002.

5
P. Sanders. Berechnungen mit großen Datenmengen. In Jahrbuch der Max-Planck-Gesellschaft, pages 534-540. MPG, 1999.

6
P. Sanders and T. Worsch. Parallele Programmierung mit MPI - ein Praktikum. Logos Verlag Berlin, 1997. ISBN 3-931216-76-4.

7
P. Sanders. Load Balancing Algorithms for Parallel Depth First Search (In German: Lastverteilungsalgorithmen für parallele Tiefensuche). Number 463 in Fortschrittsberichte, Reihe 10. VDI Verlag, Berlin, 1997.

8
B. Beckert, A. Bell, and P. Sanders. Gedichtgenerator -- Ein Anwendungsbeispiel für natürlichsprachliche Texterzeugung. In Aus Neugier wird Wissenschaft - Illustrierte Teilnehmerbeiträge aus 25 Jahren Jugend forscht. Elektor Verlag, 1990.

9
P. Sanders. Mr. Line lernt Schreiben -- Grafiktexte mit TXTGRA. In S. Egner and M. Sperber, editors, Die Grafik-Connection, pages 131-154. Heim Verlag, 1990.

Selected Other Papers

1
P. Sanders and D. Steurer. An Asymptotic Approximation Scheme for Multigraph Edge Coloring. submitted for publication, July 2004.

2
P. Sanders. Parallelizing NP-Complete Problems Using Tree Shaped Computations. In Journées de l'Informatique Messine (JIM), Metz, may 1999. invited talk.

3
P. Sanders. A Scalable Parallel Tree Search Library. In S. Ranka, editor, 2nd Workshop on Solving Irregular Problems on Distributed Memory Machines, Honolulu, Hawaii, 1996.

4
P. Sanders and T. Worsch. Konvergente lokale Lastverteilungsverfahren und ihre Modellierung durch Zellularautomaten. In PARS Workshop, number 14 in PARS Mitteilungen, pages 285-291, 1995.

5
P. Sanders. Flaschenhalsfreie parallele Priority queues. In PARS Workshop, Potsdam, number 13 in PARS Mitteilungen, pages 10-19, September 1994. Improved results in Irregular'95 and JPDC.

6
P. Sanders. Randomized static load balancing for tree shaped computations. In Workshop on Parallel Processing, TR Universität Clausthal, pages 58-69, Lessach, Österreich, 1994. ISSN 0943-3805.

7
P. Sanders. Portable parallele Baumsuchverfahren: Entwurf einer effizienten Bibliothek. In Transputer Anwender Treffen, pages 168-177, Aachen, 1994. IOS Press.

8
P. Sanders. Analysis of random polling dynamic load balancing. Technical Report IB 12/94, Universität Karlsruhe, Fakultät für Informatik, April 1994.

9
P. Sanders. Suchalgorithmen auf SIMD-Rechnern - Weitere Ergebnisse zu Polyautomaten. Diplomarbeit, Universität Karlsruhe, August 1993.


Peter Sanders
Mon Jan 17 15:59:07 MET 2005