Algorithmics and Computational Complexity
2024
Articles
V.
Froese and
M.
Renken,
"Terrain-like Graphs and the Median Genocchi Numbers"
,
European Journal of Combinatorics,
vol. 115,
pp. 103780,
2024.
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
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.
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.
Contribution to Proceedings
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.
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.
Articles
R.
Bevern,
R. G.
Downey,
M. R.
Fellows,
S.
Gaspers and
F. A.
Rosamond,
"Myhill-Nerode methods for hypergraphs"
,
Algorithmica.
Springer.
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.
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.
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,
2023.
M.
Bentert and
A.
Nichterlein,
"Parameterized Complexity of Diameter"
,
Algorithmica,
vol. 85,
no. 2,
pp. 325–351,
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
Thesis
D. L.
Tran,
"Expanding the Graph Parameter Hierarchy",
TU Berlin,
Sep.
2022.
S.
Bruchhold,
"A Simple and Robust Measure of Triadic Closure: Algorithmic and Structural Aspects",
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.
Contribution to Proceedings
N.
Boehmer and
T.
Koana,
"The Complexity of Finding Fair Many-to-One Matchings"
in Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP '22),
Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
pp. 27:1–27:18.
R.
Bredereck,
A.
Kaczmarczyk,
J.
Luo,
R.
Niedermeier and
F.
Sachse,
"On Improving Resource Allocations by Sharing"
in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22),
2022.
N.
Boehmer,
M.
Brill and
U.
Schmidt-Kraepelin,
"Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences"
in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22),
IFAAMAS,
2022.
pp. 136–144.
M.
Bentert,
N.
Boehmer,
K.
Heeger and
T.
Koana,
"Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences"
in Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT '22),
Springer,
2022.
pp. 436–453.
Master-Thesis
L.
Glessen,
"Algorithmic Approaches to Cluster Editing on Multipartite Hypergraphs",
MasterThesis,
TU Berlin,
2022.
Contribution to Proceedings
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.