Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

Christoph Grüne Computer Science 1 Dept. of Computer Science RWTH Aachen University Ahornstrasse 55, E1, Room 4021 D-52074 Aachen, Germany Phone: +49 241 80 21104 Email: [lastname][AT]algo.rwth-aachen.de

---

Websites

https://reductions.network

On this website many reductions and problems for various complexity classes are presented. If you are searching for information on a reduction or problem, you will probably find, what you are looking for. And if not, I am always happy to receive contributions!

---

Publications

• Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization.
  with Lasse Wulf
  arXiv, 2024
  [arXiv]


• The Complexity Classes of Hamming Distance Recoverable Robust Problems.
  LATIN 2024
  [conference] [arXiv]


• The Complexity of Online Graph Games.
  with Janosch Fuchs and Tom Janßen
  SOFSEM 2024
  [conference] [arXiv]


• The Complexity of Graph Exploration Games.
  with Janosch Fuchs and Tom Janßen
  arXiv, 2023
  [arXiv]


• Solving the Dial-a-Ride Problem for Railway Traffic by Means of Heuristics.
  with Stephan Zieger
  SMARTGREENS/VEHITS (Selected Papers) 2022
  [journal]


• Demand-responsive Scheduling in Railway Transportation.
  with Stephan Zieger
  VEHITS 2022
  [conference]