Algorithmics and Computational Complexity

Publications

2024

Articles
V. Froese and M. Renken, "Terrain-like Graphs and the Median Genocchi Numbers" , European Journal of Combinatorics, vol. 115, pp. 103780, 2024.

R. Bevern, R. G. Downey, M. R. Fellows, S. Gaspers and F. A. Rosamond, "Myhill-Nerode methods for hypergraphs" , Algorithmica. Springer.

2023

Master-Thesis
C. Schubert, "Leveraging Graph Structure to Untangle Temporal Networks Efficiently", MasterThesis, TU Berlin, Oct. 2023.
C. Wallisch, "Placing Green Bridges to Reconnect Habitats Densely: Algorithms and Complexity", BachelorThesis, TU Berlin, Apr. 2023.
Articles
B. Jain, V. Froese and D. Schultz, "An Average-Compress Algorithm for the Sample Mean Problem Under Dynamic Time Warping" , Journal of Global Optimization, vol. 86, pp. 885–903, 2023.
V. Froese, P. Kunz and P. Zschoche, "Disentangling the Computational Complexity of Network Untangling" , Theory of Computing Systems, 2023.
V. Froese, B. Jain, M. Rymar and M. Weller, "Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series" , Algorithmica, vol. 85, pp. 492–508, 2023.
M. Bentert and A. Nichterlein, "Parameterized Complexity of Diameter" , Algorithmica, vol. 85, no. 2, pp. 325–351, 2023.
M. Bentert, R. Bevern, T. Fluschnik, A. Nichterlein and R. Niedermeier, "Polynomial-time data reduction for weighted problems beyond additive goal functions" , Discrete Applied Mathematics, vol. 328, pp. 117–133, 2023.
T. Koana, V. Froese and R. Niedermeier, "The Complexity of Binary Matrix Completion Under Diameter Constraints" , Journal of Computer and System Sciences, vol. 132, pp. 45–67, 2023.
Contribution to Proceedings
K. Heeger, A. Nichterlein and R. Niedermeier, "Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions" in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 23), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 35:1–35:19.
V. Froese and C. Hertrich, "Training Neural Networks is NP-Hard in Fixed Dimension" in 37th Conference on Neural Information Processing Systems (NeurIPS '23), 2023.
Articles
B. Jain, V. Froese and D. Schultz, "An Average-Compress Algorithm for the Sample Mean Problem Under Dynamic Time Warping" , Journal of Global Optimization, 2023.
N. Boehmer, T. Koana and R. Niedermeier, "A Refined Complexity Analysis of Fair Districting over Graphs" , Autonomous Agents and Multi-Agent Systems, vol. 37, no. 1, pp. 13, 2023.

2022

Thesis
S. Bruchhold, "A Simple and Robust Measure of Triadic Closure: Algorithmic and Structural Aspects", TU Berlin, Sep. 2022.
D. L. Tran, "Expanding the Graph Parameter Hierarchy", TU Berlin, Sep. 2022.
Master-Thesis
S. Bruchhold, "A Simple and Robust Measure of Triadic Closure: Algorithmic and Structural Aspects", BachelorThesis, TU Berlin, Sep. 2022.
Thesis
E. Deltl, "Algorithmic Complexity of Bi-Criteria Multilevel Committee Election", TU Berlin, May 2022.
Master-Thesis
E. Deltl, "Algorithmic Complexity of Bi-Criteria Multilevel Committee Election", BachelorThesis, TU Berlin, May 2022.
L. Glessen, "Algorithmic Approaches to Cluster Editing on Multipartite Hypergraphs", MasterThesis, TU Berlin, 2022.
Contribution to Proceedings
V. Froese, L. Kellerhals and R. Niedermeier, "Modification-Fair Cluster Editing" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 6631–6638.
L. Kellerhals, T. Koana and P. Kunz, "Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees" in Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 19:1–19:14.
N. Boehmer, P. Faliszewski, R. Niedermeier, S. Szufa and T. Wąs, "Understanding Distance Measures Among Elections" in Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), ijcai.org, 2022. pp. 102–108.
A. Figiel, V. Froese, A. Nichterlein and R. Niedermeier, "There and Back Again: On Applying Data Reduction Rules by Undoing Others" in Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 53:1–53:15.
N. Boehmer, K. Heeger and R. Niedermeier, "Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 4851–4858.