Journal

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.

DOI: 10.1007/s10458-022-09594-2
Weblink: https://arxiv.org/abs/2102.11864
File: https://arxiv.org/abs/2102.11864

Show details

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.

DOI: 10.1016/J.JCSS.2022.10.001
Weblink: https://arxiv.org/abs/2002.05068
File: https://arxiv.org/abs/2002.05068

Show details

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.

DOI: 10.1007/s10898-023-01294-9
File: https://arxiv.org/abs/1909.13541

Show details

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

DOI: 10.1007/s00453-015-9977-x
Weblink: http://arxiv.org/abs/1211.1299

Show details

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.

DOI: 10.1016/j.dam.2022.11.018
File: https://doi.org/10.1016/j.dam.2022.11.018

Show details

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.

DOI: 10.1007/s00453-022-01038-3
File: https://arxiv.org/abs/1903.03003

Show details

M. Bentert and A. Nichterlein, "Parameterized Complexity of Diameter" , Algorithmica, vol. 85, no. 2, pp. 325–351, 2023.

DOI: 10.1007/s00453-022-01032-9
Weblink: https://doi.org/10.1007/s00453-022-01032-9
File: https://doi.org/10.1007/s00453-022-01032-9

Show details

P. Zschoche, "A faster parameterized algorithm for temporal matching" , Information Processing Letters, vol. 174, pp. 106181, 2022.

DOI: 10.1016/j.ipl.2021.106181
Weblink: https://arxiv.org/abs/2010.10408
File: https://arxiv.org/abs/2010.10408

Show details

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.

DOI: 10.1145/3546605
Weblink: arxiv.org/abs/2009.14171

Show details

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.

Weblink: https://arxiv.org/abs/2010.04643
File: https://arxiv.org/abs/2010.04643

Show details

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.

DOI: 10.1016/J.JCSS.2021.12.002
Weblink: https://arxiv.org/abs/1910.03409
File: https://arxiv.org/abs/1910.03409

Show details

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.

DOI: 10.1287/ijoc.2020.1045
Weblink: https://arxiv.org/abs/1706.03177

Show details

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.

DOI: 10.1016/J.IC.2022.104943
Weblink: https://arxiv.org/abs/1911.09379
File: https://arxiv.org/abs/1911.09379

Show details

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.

DOI: 10.1613/JAIR.1.13547
Weblink: https://arxiv.org/abs/2105.08675
File: https://arxiv.org/abs/2105.08675

Show details

J. Luo, H. Molter, A. Nichterlein and R. Niedermeier, "Parameterized Dynamic Cluster Editing" , Algorithmica, vol. 83, no. 1, pp. 1–44, 2021. Springer.

DOI: 10.1007/S00453-020-00746-Y
Weblink: https://arxiv.org/abs/1810.06625

Show details

M. Bentert and M. Weller, "Tree Containment With Soft Polytomies" , Journal of Graph Algorithms and Applications, vol. 25, no. 1, pp. 417–436, 2021.

DOI: 10.7155/JGAA.00565
Weblink: https://hal.archives-ouvertes.fr/hal-01734619

Show details

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.

DOI: 10.1007/s00453-021-00831-w
Weblink: https://arxiv.org/abs/1909.06437

Show details

G. B. Mertzios, H. Molter and V. Zamaraev, "Sliding Window Temporal Graph Coloring" , Journal of Computer and System Sciences, 2021. Elsevier.

Weblink: https://arxiv.org/abs/1811.04753

Show details

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.

DOI: 10.1016/J.ARTINT.2020.103403
Weblink: https://arxiv.org/abs/1707.01417

Show details

V. Froese and M. Renken, "Persistent Graphs and Cyclic Polytope Triangulations" , Combinatorica, vol. 41, pp. 407–423, 2021. Springer.

DOI: 10.1007/S00493-020-4369-5
Weblink: https://arxiv.org/pdf/1911.05012.pdf

Show details

H. Molter, R. Niedermeier and M. Renken, "Isolation concepts applied to temporal clique enumeration" , Network Science, vol. 9, no. S1, pp. S83–S105, 2021.

DOI: 10.1017/nws.2020.38
Weblink: https://fpt.akt.tu-berlin.de/publications/temporal-isolated-cliques.pdf

Show details

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.

DOI: 10.1007/S00224-021-10057-6
Weblink: https://arxiv.org/abs/2005.14620

Show details

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.

DOI: 10.1016/j.tcs.2021.04.002
Weblink: https://arxiv.org/abs/1912.04392

Show details

T. Koana and A. Nichterlein, "Detecting and enumerating small induced subgraphs in c-closed graphs" , Discrete Applied Mathematics, vol. 302, pp. 198–207, 2021. Elsevier.

DOI: 10.1016/J.DAM.2021.06.019
Weblink: https://arxiv.org/abs/2007.12077

Show details

T. Koana, V. Korenwein, A. Nichterlein, R. Niedermeier and P. Zschoche, "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments" , ACM Journal of Experimental Algorithmics, vol. 24, pp. 1–30, 2021. ACM.

DOI: https://doi.org/10.1145/3439801
Weblink: https://dl.acm.org/doi/abs/10.1145/3439801

Show details