Algorithmik und Komplexitätstheorie

Zeitschriften

2024

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

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.
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.
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.
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.
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.
M. Bentert and A. Nichterlein, "Parameterized Complexity of Diameter" , Algorithmica, vol. 85, no. 2, pp. 325–351, 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.

2022

P. Zschoche, "A faster parameterized algorithm for temporal matching" , Information Processing Letters, vol. 174, pp. 106181, 2022.
N. Boehmer and K. Heeger, "A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas" , ACM Transactions on Economics and Computation, vol. 10, no. 2, pp. 9:1–9:53, 2022.
K. Heeger, D. Hermelin, G. B. Mertzios, H. Molter, R. Niedermeier and D. Shabtay, "Equitable Scheduling on a Single Machine" , Journal of Scheduling, 2022. Springer.
M. Bentert, K. Heeger and D. Knop, "Length-bounded cuts: Proper interval graphs and structural parameters" , Journal of Computer and System Sciences, vol. 126, pp. 21-43, 2022.
M. Bentert, R. Bevern, A. Nichterlein, R. Niedermeier and P. V. Smirnov, "Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments" , Informs Journal on Computing, vol. 34, no. 1, pp. 55--75, 2022.
R. Bredereck, K. Heeger, D. Knop and R. Niedermeier, "Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters" , Information and Computation, pp. 104943, 2022.
V. Froese, C. Hertrich and R. Niedermeier, "The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality" , Journal of Artificial Intelligence Research, vol. 74, pp. 1775–1790, 2022.

2021

M. Bentert, R. Haag, C. Hofer, T. Koana and A. Nichterlein, "Parameterized Complexity of Min-Power Asymmetric Connectivity" , Theory of Computing Systems, vol. 65, no. 7, pp. 1141–1142, 2021.
M. Bentert and M. Weller, "Tree Containment With Soft Polytomies" , Journal of Graph Algorithms and Applications, vol. 25, no. 1, pp. 417–436, 2021.
G. B. Mertzios, H. Molter and V. Zamaraev, "Sliding Window Temporal Graph Coloring" , Journal of Computer and System Sciences, 2021. Elsevier.
R. Bredereck, P. Faliszewski, A. Kaczmarczyk, R. Niedermeier, P. Skowron and N. Talmon, "Robustness among multiwinner voting rules" , Artificial Intelligence, vol. 290, pp. 103403, 2021.
V. Froese and M. Renken, "Persistent Graphs and Cyclic Polytope Triangulations" , Combinatorica, vol. 41, pp. 407–423, 2021. Springer.
J. Luo, H. Molter, A. Nichterlein and R. Niedermeier, "Parameterized Dynamic Cluster Editing" , Algorithmica, vol. 83, no. 1, pp. 1–44, 2021. Springer.
A. Casteigts, A. Himmel, H. Molter and P. Zschoche, "The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints" , Algorithmica, vol. 83, no. 9, pp. 2754–2802, 2021. Springer.
K. Heeger, A. Himmel, F. Kammer, R. Niedermeier, M. Renken and A. Sajenko, "Multistage graph problems on a global budget" , Theoretical Computer Science, vol. 868, pp. 46-64, 2021.