Dr. rer. nat. Christian Scheideler

Member of the research group Theoretical Computer Science, AG Meyer auf der Heide

Research Areas:

• Routing in fixed-connection and mobile networks
• Job shop scheduling
• Storage networks
• Parallel and distributed algorithms
• Randomized algorithms and stochastic processes
• Combinatorics and discrete mathematics

Projects:

• DFG Special Research Program 376 »Massively Parallel Systems: Algorithms · Design Methods · Applications«
• EU ESPRIT Long Term Research Project 20244 »Algorithms and Complexity in Information Technology« (ALCOM-IT) (Paderborn)

Address:

Heinz Nixdorf Institute and
Department of Mathematics and Computer Science
Paderborn University
D-33095 Paderborn
Germany

Published Books:

• C. Scheideler.
  Universal Routing Strategies for Interconnection Networks
  Lecture Notes in Computer Science 1390, Springer Verlag, 1998.

Available Papers:

• A. Brinkmann, K. Salzwedel, C. Scheideler.
  Efficient, Distributed Data Placement Strategies for Storage Area Networks
  To appear in: Proc. 12 ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2000.
  
  
• A. Czumaj, C. Scheideler.
  A New Algorithmic Approach to the General Lovasz Local Lemma with Applications to Schedulung and Satisfiability Problems (Full Version)
  To appear in: Proc. 32 ACM Symposium on Theory of Computing (STOC) , 2000.
  
  
• A. Czumaj, C. Scheideler.
  Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma (Full Version)
  To appear in: Proc. 11 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000.
  
  
• P. Berenbrink, A. Brinkmann, C. Scheideler.
  Design of the PRESTO Multimedia Storage Network (Extended Abstract)
  In: International Workshop on Communication and Data Management in Large Networks (CDMLarge), 1999.
  
  
• P. Berenbrink, M. Riedel, C. Scheideler.
  Simple Competitive Request Scheduling Strategies (Extended Abstract)
  In: Proc. 11 ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1999.
  
  
• C. Scheideler, B. Vöcking.
  From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols (Full Version)
  Extended Abstract appeared in: Proc. 31 ACM Symposium on Theory of Computing (STOC), pp. 215-224, 1999.
  
  
• P. Berenbrink, C. Scheideler.
  Locally Efficient On-Line Strategies for Routing Packets along Fixed Paths (Preliminary Version)
  In: Proc. 10 ACM-SIAM Symposium on Discrete ALgorithms (SODA), pp. 112-121, 1999.
  
  
• M. Adler, C. Scheideler.
  Efficient Communication Strategies for Ad-Hoc Wireless Networks (Full Version)
  Extended Abstract appeared in: Proc. 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 259-268, 1998.
  
  
• U. Feige, C. Scheideler.
  Improved Bounds for Acyclic Job Shop Scheduling (Full Version)
  Extended abstract appeared in: Proc. 28th ACM Symposium on Theory of Computing (STOC), pp. 624-233, 1998.
  
  
• M. Flammini, C. Scheideler.
  Simple, Efficient Routing Schemes for All-Optical Networks (Full Version)
  Extended abstract appeared in: Proc. 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 170-179, 1997.
  
  
• S. Bock, F. Meyer auf der Heide, C. Scheideler.
  Optimal Wormhole Routing in the (n,d)-Torus (Full Version)
  In: Proc. 11th International Parallel Processing Symposium (IPPS), 1997.
  
  
• F. Meyer auf der Heide, C. Scheideler.
  Communication in Parallel Systems (Full Version)
  In: 23rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) '96, pp. 16-33, 1996.
  
  
• F. Meyer auf der Heide, C. Scheideler.
  Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols (Full Version)
  Extended abstract appeared in: Proc. 37th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 370-379, 1996.
  
  
• C. Scheideler, B. Vöcking.
  Universal Continuous Routing Strategies (Full Version)
  Extended abstract appeared in: Proc. 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 142-151, 1996.
  
  
• R. Cypher, F. Meyer auf der Heide, C. Scheideler, B. Vöcking.
  Universal Algorithms for Store-and-Forward and Wormhole Routing (Extended Abstract)
  In: Proc. 26th ACM Symposium on Theory of Computing (STOC), pp. 356-365, 1996.
  
  
• F. Meyer auf der Heide, C. Scheideler.
  Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks (Extended Abstract)
  In: Proc. 3rd European Symposium on Algorithms (ESA), pp. 341-354, 1995.
  
  
• F. Meyer auf der Heide, C. Scheideler.
  Space-Efficient Routing in Vertex-Symmetric Networks (Full Version)
  Extended abstract appeared in: Proc. 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 137-146, 1995.
  
  
• F. Meyer auf der Heide, C. Scheideler, V. Stemann.
  Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations (Full Version)
  Extended abstract appeared in: Proc. 12th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 267-278, 1995.