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.

2023

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

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

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.
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.
V. Froese, P. Kunz and P. Zschoche, "Disentangling the Computational Complexity of Network Untangling" , Theory of Computing Systems, 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.

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.
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.
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.
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.
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.
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.
P. Zschoche, "A faster parameterized algorithm for temporal matching" , Information Processing Letters, vol. 174, pp. 106181, 2022.

2021

J. Luo, H. Molter, A. Nichterlein and R. Niedermeier, "Parameterized Dynamic Cluster Editing" , Algorithmica, vol. 83, no. 1, pp. 1–44, 2021. Springer.
M. Bentert and M. Weller, "Tree Containment With Soft Polytomies" , Journal of Graph Algorithms and Applications, vol. 25, no. 1, pp. 417–436, 2021.
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.
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.
H. Molter, R. Niedermeier and M. Renken, "Isolation concepts applied to temporal clique enumeration" , Network Science, vol. 9, no. S1, pp. S83–S105, 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.