Institute of Theoretical Informatics, Algorithmics

Dr. Bastian Katz

former scientific assistant

Dr. Bastian Katz Dr. rer. nat. Bastian Katz

eMail post [at] bastiankatz [dot] de


Since July 2010, I work as Optimization Analyst at Axxom.

Research Interests

I am interested in any problem regarding combinatorial optimization, especially in the fields of graph theory and/or geometry:

  • algorithmic concepts in graph theory, e.g. matroids in graphs (graph rigidity, switch graphs, matchings)
  • network design and partitioning problems
  • graph drawing
  • distributed algorithms and models for ad hoc and sensor networks (positioning, scheduling)
  • algorithm engineering in computation of shortest paths and maximum flows

Selected Publications

  • Gateway Decompositions for Constrained Reachability Problems.
    SEA'10, joint work wit M Krug, A Lochbihler, I Rutter, G Snelting, D Wagner. to appear 2010 in Springer LNCS.
  • Parallel Computation of Best Connections in Public Transportation Networks. pdf (TR)
    IPDPS'10, joint work with D Delling, T Pajor. to appear 2010.
  • Manhattan-Geodesic Embedding of Planar Graphs. pdf
    GD'09, joint work with M Krug, I Rutter, A Wolff. Springer LNCS vol. 5849, pg. 207-218, 2009.
  • An Algorithmic Study of Switch Graphs. pdf
    WG'09, joint work with I Rutter, G Woeginger. Springer LNCS vol. 5911, pg. 226-237, 2009
  • Efficient Scheduling of Data Harvesting Trees. pdf
    ALGOSENSORS'08, joint work with S Mecke, D Wagner. Springer LNCS vol. 5389, pg. 43-56, 2008.
  • Positioning and Scheduling of Wireless Sensor Networks - Models, Complexity, and Scalable Algorithms. pdf.
    Dissertation, 2009.

complete list