DKE research theme

Algorithms, Complexity, and Optimization (ALGOPT)

Designing efficient algorithms helps to explore the limits of what computers can achieve with real-world computational power.

Selected publications

  • Angelini, P., Chaplick, S., Cornelsen, S., Lozzo, G. D., & Roselli, V. (2019). Morphing Contact Representations of Graphs. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129, pp. 10:1-10:16). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics (LIPIcs) Vol. 129 https://doi.org/10.4230/LIPICS.SOCG.2019.10
  • Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Geissmann, B., Graf, D., Labourel, A., & Mihalák, M. (2020). Collaborative delivery with energy-constrained mobile robots. Theoretical Computer Science, 810, 2-14. https://doi.org/10.1016/j.tcs.2017.04.018
  • Bonnet, E., Escoffier, B., Paschos, V., & Stamoulis, G. (2018). Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discrete Optimization, 27, 26-56. https://doi.org/10.1016/j.disopt.2017.09.001
  • Bot, R., Grad, S. M., Meier, D., & Staudigl, M. (2021). Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure. Advances in Nonlinear Analysis, 10(1), 450-476. https://doi.org/10.1515/anona-2020-0143
  • Chaplick, S., Fomin, F., Golovach, P. A., Knop, D., & Zeman, P. (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. Siam Journal on Discrete Mathematics, 35(2), 840-892. https://doi.org/10.1137/19M1299001
  • Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. Journal of Graph Theory, 91(4), 365-394. https://doi.org/10.1002/JGT.22436
  • Chen, C., Giessler, P., Mamageishvili, A., Mihalák, M., & Penna, P. (2020). Sequential Solutions in Machine Scheduling Games. In X. Chen, N. Gravin, M. Hoefer, & R. Mehta (Eds.), Web and Internet Economics: Proceedings of the 16th International Conference on Web and Internet Economics (WINE) (Vol. 12495, pp. 309-322). Springer Nature. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-030-64946-322
  • de Campos, C. P., Stamoulis, G., & Weyland, D. (2020). A structured view on weighted counting with relations to counting, quantum computation and applications. Information and Computation, 275, [104627]. https://doi.org/10.1016/j.ic.2020.104627
  • Dvurechensky, P., Shtern, S., & Staudigl, M. (2021). First-Order Methods for Convex Optimization. EURO Journal on Computational Optimization, 9, [100015]. https://doi.org/10.1016/j.ejco.2021.100015
  • Jones, M., Kelk, S., & Stougie, L. (2021). Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm. Journal of Computer and System Sciences, 117, 165-181. https://doi.org/10.1016/j.jcss.2020.10.003
  • Kelk, S., & Linz, S. (2019). A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees. Siam Journal on Discrete Mathematics, 33(3), 1556-1574. https://doi.org/10.1137/18M122724X
  • Kelk, S., & Stamoulis, G. (2019). Integrality gaps for colorful matchings. Discrete Optimization, 32, 73-92. https://doi.org/10.1016/j.disopt.2018.12.003
  • Mihalák, M., & Pont, M. (2019). On Sorting with a Network of Two Stacks. In V. Cacchiani, & A. Marchetti-Spaccamela (Eds.), 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) (Vol. 75, pp. 3:1-3:12). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. OASICS https://doi.org/10.4230/OASIcs.ATMOS.2019.3
  • Musegaas, M., Schlicher, L. & Blok, H. (2022). Stackelberg production-protection games: Defending crop production against intentional attacks. European Journal of Operational Research, 297(1), 102-119. https://doi.org/10.1016/j.ejor.2021.04.012.
  • Van Iersel, L., Jones, M., & Kelk, S. (2019). A Third Strike Against Perfect Phylogeny. Systematic Biology, 68(5), 814-827. https://doi.org/10.1093/sysbio/syz009
  • Westerink-Duijzer, L. E., Schlicher, L. P. J., & Musegaas, M. (2020). Core Allocations for Cooperation Problems in Vaccination. Production and Operations Management, 29(7), 1720-1737. https://doi.org/10.1111/poms.13184

See all DKE publications