Staff profile

I received a PhD in Computer Science from Technische Universität München in 1999. From 2000 to 2004 I was an Assistant Professor in Theory of Communication Networks at ETH Zürich. From September 2004 to September 2021 I was with the Department of Computer Science (later renamed as School of Informatics and then School of Computing and Mathematical Sciences) at University of Leicester, first as Reader and then, from April 2007, as Professor. In September 2021 I joined the Department of Computer Science at Durham University as Professor.

Publications

You can check my DBLP page or my Google Scholar page.

Research Groups

• NESTiD: Network Engineering, Science and Theory in Durham
• ACiD: Algorithms and Complexity in Durham

• Algorithmic aspects of communication networks
• Time-varying graphs and networks
• Computing with explorable uncertainty
• Approximation and on-line algorithms for combinatorial optimisation problems

Conference Paper

• Scheduling with Obligatory Tests
  
  Dogeas, K., Erlebach, T., & Liang, Y.-C. (2024). Scheduling with Obligatory Tests. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024) (pp. 48:1-48:14). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.ESA.2024.41
• Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
  
  Bampis, E., Dogeas, K., Erlebach, T., Megow, N., Schlöter, J., & Trehan, A. (2024). Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024 (pp. 17:1-17:21). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.17
• Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization
  
  Erlebach, T., Morawietz, N., & Wolf, P. (2024). Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (pp. 12:1-12:16). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2024.12
• Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
  
  Dogeas, K., Erlebach, T., Kammer, F., Meintrup, J., & Moses Jr, W. K. (2024). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (pp. 55:1-55:18). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2024.62
• List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs
  
  Baklan Sen, B., Diner, Öznur Y., & Erlebach, T. (2023). List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. In Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023) (pp. 168-181). Springer. https://doi.org/10.1007/978-3-031-49190-0_12
• Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
  
  Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2022). Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (pp. 49:1-49:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.49
• Parameterized temporal exploration problems
  
  Erlebach, T., & Spooner, J. T. (2022). Parameterized temporal exploration problems. In J. Aspnes & O. Michail (Eds.), LIPIcs (pp. 15:1-15:17). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.sand.2022.15
• Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty
  
  Bampis, E., Dürr, C., Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2021). Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. In LIPIcs (pp. 10:1-10:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.esa.2021.10
• Exploration of k-Edge-Deficient Temporal Graphs
  
  Erlebach, T., & Spooner, J. T. (2021). Exploration of k-Edge-Deficient Temporal Graphs. In Lecture Notes in Computer Science (pp. 371-384). Springer Verlag. https://doi.org/10.1007/978-3-030-83508-8_27
• Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
  
  Erlebach, T., Hoffmann, M., & de Lima, M. S. (2021). Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. In LIPIcs (pp. 27:1-27:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.stacs.2021.27

Journal Article

• Classification and evaluation of the algorithms for vector bin packing
  
  Mommessin, C., Erlebach, T., & Shakhlevich, N. V. (2025). Classification and evaluation of the algorithms for vector bin packing. Computers & Operations Research, 173, Article 106860. https://doi.org/10.1016/j.cor.2024.106860
• A cop and robber game on edge-periodic temporal graphs
  
  Erlebach, T., Morawietz, N., Spooner, J. T., & Wolf, P. (2024). A cop and robber game on edge-periodic temporal graphs. Journal of Computer and System Sciences, 144, Article 103534. https://doi.org/10.1016/j.jcss.2024.103534
• Round-competitive algorithms for uncertainty problems with parallel queries
  
  Erlebach, T., Hoffmann, M., & de Lima, M. S. (2023). Round-competitive algorithms for uncertainty problems with parallel queries. Algorithmica, 85(2), 406-443. https://doi.org/10.1007/s00453-022-01035-6
• Parameterized temporal exploration problems
  
  Erlebach, T., & Spooner, J. T. (2023). Parameterized temporal exploration problems. Journal of Computer and System Sciences, 135, 73-88. https://doi.org/10.1016/j.jcss.2023.01.003
• Exploration of k-Edge-Deficient Temporal Graphs
  
  Erlebach, T., & Spooner, J. T. (2022). Exploration of k-Edge-Deficient Temporal Graphs. Acta Informatica, 59(4), 387-407. https://doi.org/10.1007/s00236-022-00421-5
• Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings
  
  Luo, K., Erlebach, T., & Xu, Y. (2022). Car-Sharing between Two Locations: Online Scheduling with Flexible Advance Bookings. Discrete Applied Mathematics, 313, 53-66. https://doi.org/10.1016/j.dam.2022.01.016
• On the fast delivery problem with one or two packages
  
  Carvalho, I. A., Erlebach, T., & Papadopoulos, K. (2021). On the fast delivery problem with one or two packages. Journal of Computer and System Sciences, 115, 246-263. https://doi.org/10.1016/j.jcss.2020.09.002