Algorithmics and Computational Complexity

Prof. Dr. Rolf Niedermeier

 

 

 

Curriculum Vitae

March 2022Rolf Niedermeier unexpectedly passed away
2010 - March 2022Chair Algorithmics and Computational Complexity, TU Berlin
2004-2010Chair Theoretical Computer Science I, Friedrich-Schiller-Universität Jena
2002-2004Head of Emmy Noether research group Eberhard-Karls-Universität Tübinge
1999-2002Eberhard-Karls-Universität Tübingen (Prof. Lange)
1998Charles University Prague (Prof. Nešetříl)
1994-1997Eberhard-Karls-Universität Tübingen (Prof. Lange)
1991-1994TU München (Prof. Brauer, Prof. Lange)

Research projects

started November 2021COMSOC-MPMS: Computational Social Choice: Multiple Preference Profiles and Multiple Solutions
started March 2021DiPa: The Art of Difference Parameterization in Multivariate Algorithmics
started April 2018MaMu: Matching under Preferences: Multimodal Views and Domain Restrictions
2018 - 2022TORE: Trade-offs in Parameterized Data Reduction
2018 - 2022MATE: Multivariate Algorithmics for Temporal Graph Problems
started December 2017FPTinP: More Efficient Algorithms for Polynomial-Time Solvable Graph Problems
started October 2016AFFA: Algorithms for Fair Allocations
2012 -DAMM: Data Reduction in Parameterized Algorithmics - New Models and Methods
2012 -DAPA: Data Driven Parameterized Algorithmics for Graph Modification Problems
2010 - 2014DARE: Data Reduction and Problem Kernels
2009 - 2017PAWS: Parameterized Algorithmics for Voting Systems
2008 - 2013AREG: Algorithms for Generating Quasi-Regular Structures in Graphs
2007 - 2014PABI: Parameterized Algorithmics for Bioinformatics

Publications

2023

Boehmer, Niclas; Koana, Tomohiro; Niedermeier, Rolf
A Refined Complexity Analysis of Fair Districting over Graphs
Autonomous Agents and Multi-Agent Systems, 37 (1) :13
2023
Koana, Tomohiro; Froese, Vincent; Niedermeier, Rolf
The Complexity of Binary Matrix Completion Under Diameter Constraints
Journal of Computer and System Sciences, 132 :45–67
2023
Bentert, Matthias; Bevern, René; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf
Polynomial-time data reduction for weighted problems beyond additive goal functions
Discrete Applied Mathematics, 328 :117–133
2023

2022

Bredereck, Robert; Kaczmarczyk, Andrzej; Luo, Junjie; Niedermeier, Rolf; Sachse, Florian
On Improving Resource Allocations by Sharing
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)
2022
Boehmer, Niclas; Faliszewski, Piotr; Niedermeier, Rolf; Szufa, Stanisław; Wąs, Tomasz
Understanding Distance Measures Among Elections
Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), Page 102–108
Publisher: ijcai.org
2022
Figiel, Aleksander; Froese, Vincent; Nichterlein, André; Niedermeier, Rolf
There and Back Again: On Applying Data Reduction Rules by Undoing Others
, Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22)Volume244fromLeibniz International Proceedings in Informatics (LIPIcs), Page 53:1–53:15
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
Boehmer, Niclas; Heeger, Klaus; Niedermeier, Rolf
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), Page 4851–4858
2022
Bredereck, Robert; Heeger, Klaus; Knop, Dušan; Niedermeier, Rolf
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Information and Computation :104943
2022
ISSN: 0890-5401
Bentert, Matthias; Bevern, René; Nichterlein, André; Niedermeier, Rolf; Smirnov, Pavel V.
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Informs Journal on Computing, 34 (1) :55--75
2022
Froese, Vincent; Hertrich, Christoph; Niedermeier, Rolf
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Journal of Artificial Intelligence Research, 74 :1775–1790
2022
Fluschnik, Till; Kunz, Pascal; Niedermeier, Rolf; Renken, Malte
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '22)
2022
Heeger, Klaus; Hermelin, Danny; Mertzios, George B.; Molter, Hendrik; Niedermeier, Rolf; Shabtay, Dvir
Equitable Scheduling on a Single Machine
Journal of Scheduling
2022
Publisher: Springer
Kreisel, Luca; Boehmer, Niclas; Froese, Vincent; Niedermeier, Rolf
Equilibria in Schelling Games: Computational Hardness and Robustness
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 761–769
Publisher: IFAAMAS
2022
Boehmer, Niclas; Heeger, Klaus; Niedermeier, Rolf
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22)Volume241fromLIPIcs, Page 21:1–21:15
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
Schulz, Hjalmar; Nichterlein, André; Niedermeier, Rolf; Weyand, Christopher
Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time
, Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22)Volume249fromLeibniz International Proceedings in Informatics (LIPIcs), Page 25:1–25:14
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
Boehmer, Niclas; Koana, Tomohiro; Niedermeier, Rolf
A Refined Complexity Analysis of Fair Districting over Graphs
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 1548–1550
Publisher: IFAAMAS
2022
Boehmer, Niclas; Bredereck, Robert; Faliszewski, Piotr; Niedermeier, Rolf
A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners
Proceedings of the Second Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO '22), Page 7:1–7:10
Publisher: ACM
2022
Froese, Vincent; Kellerhals, Leon; Niedermeier, Rolf
Modification-Fair Cluster Editing
, Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)Volume36, Page 6631–6638
2022

2021

Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Niedermeier, Rolf; Skowron, Piotr; Talmon, Nimrod
Robustness among multiwinner voting rules
Artificial Intelligence, 290 :103403
2021
Figiel, Aleksander; Kellerhals, Leon; Niedermeier, Rolf; Rost, Matthias; Schmid, Stefan; Zschoche, Philipp
Optimal Virtual Network Embeddings for Tree Topologies
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architechtures
Publisher: ACM
2021
Luo, Junjie; Molter, Hendrik; Nichterlein, André; Niedermeier, Rolf
Parameterized Dynamic Cluster Editing
Algorithmica, 83 (1) :1–44
2021
Publisher: Springer
Boehmer, Niclas; Bredereck, Robert; Faliszewski, Piotr; Niedermeier, Rolf; Szufa, Stanislaw
Putting a Compass on the Map of Elections
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 59–65
Publisher: ijcai.org
2021
Boehmer, Niclas; Bredereck, Robert; Faliszewski, Piotr; Niedermeier, Rolf
Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 52–58
Publisher: ijcai.org
2021
Bentert, Matthias; Koana, Tomohiro; Niedermeier, Rolf
The Complexity of Gerrymandering over Graphs: Paths and Trees
Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Page 195–206
2021
Rymar, Maciej; Molter, Hendrik; Nichterlein, André; Niedermeier, Rolf
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
, Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '21)Volume12911fromLecture Notes in Computer Science, Page 219–231
Publisher: Springer
2021

Page 1 of 15