Markus Blumenstock, Dr.

Postdoctoral Teaching Associate
Johannes Gutenberg University Mainz
Institute of Computer Science
Staudingerweg 9
55128 Mainz
Room: 03-219
Office phone: +49 6131 39-24624
Office hours: Monday 16:00-17:00, by arrangement or just try knocking at my door

Curriculum Vitae (pdf)

Research Interests

  • Approximation algorithms
  • Maximum flow algorithms
  • Steiner trees
  • (Pseudo-)Arboricity
  • Integer Linear Programming
  • Similarity Estimation


M. Blumenstock and F. Fischer. A Constructive Arboricity Approximation Scheme. In Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020). Lecture Notes in Computer Science, Vol. 12011, pp. 51–63. Springer, 2020. DOI:

M. Blumenstock. Pseudoforest Partitions and the Approximation of Connected Subgraphs of High Density. PhD thesis, Johannes Gutenberg University Mainz, 2020. Slightly corrected version (errata).

M. Blumenstock. Fast Algorithms for Pseudoarboricity. In Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX 2016) in Arlington, Virginia, USA, January 2016, pp. 113–126. Society for Industrial and Applied Mathematics, 2016.

E. Althaus, M. Blumenstock, A. Disterhoft, A. Hildebrandt, and M. Krupp. Algorithms for the Maximum
Weight Connected k-Induced Subgraph Problem. In 8th International Conference on Combinatorial
Optimization and Applications (COCOA 2014), Wailea, Hawaii, USA, December 2014. Lecture Notes in Computer Science, Vol. 8881, pp. 268–282. Springer, 2014.