Algorithmics and Computational Complexity
Organization name Algorithmics and Computational Complexity
Office TEL 5-1
Room TEL 509D
office hoursTuesdays 17:30 - 18:30

Curriculum Vitae

since 02/2017Researcher at TU Berlin
02/2016 - 01/2017PostDoc with Prof. George Mertzios at Durham University (UK) in the group “Algorithms and Complexity in Durham” (DAAD fellowship)
12/2014PhD (Dr. rer. nat), TU Berlin, Germany.
10/2010 - 01/2016Research assistant at TU Berlin
04/2010Diploma, Friedrich-Schiller-Universität, Jena, Germany

Research interests

parameterized algorithmics
algorithm engineering
kernelization
graph problems

Publications

2023

Articles
Bentert, Matthias; Nichterlein, André
Parameterized Complexity of Diameter
Algorithmica, 85 (2) :325–351
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
Contribution to Proceedings
Heeger, Klaus; Nichterlein, André; Niedermeier, Rolf
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
, Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 23)Volume254fromLIPIcs, Page 35:1–35:19
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2023

2022

Articles
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
Contribution to Proceedings
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; Bredereck, Robert; Nichterlein, André
Combating Collusion Rings is Hard but Possible
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), Page 4843–4850
2022
Koana, Tomohiro; Komusiewicz, Christian; Nichterlein, André; Sommer, Frank
Covering Many (Or Few) Edges with k Vertices in Sparse Graphs
, Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 22)Volume219fromLIPIcs, Page 42:1–42:18
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
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

2021

Bentert, Matthias; Nichterlein, André; Renken, Malte; Zschoche, Philipp
Using a Geometric Lens to Find $k$ Disjoint Shortest Paths
, Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)Volume198fromLIPIcs, Page 26:1–26:14
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
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
Figiel, Aleksander; Himmel, Anne-Sophie; Nichterlein, André; Niedermeier, Rolf
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
, Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC '21)Volume12701fromLecture Notes in Computer Science, Page 216–230
Publisher: Springer
2021
Articles
Luo, Junjie; Molter, Hendrik; Nichterlein, André; Niedermeier, Rolf
Parameterized Dynamic Cluster Editing
Algorithmica, 83 (1) :1–44
2021
Publisher: Springer
Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André
Parameterized Complexity of Min-Power Asymmetric Connectivity
Theory of Computing Systems, 65 (7) :1141–1142
2021
Koana, Tomohiro; Nichterlein, André
Detecting and enumerating small induced subgraphs in c-closed graphs
Discrete Applied Mathematics, 302 :198–207
2021
Publisher: Elsevier
Koana, Tomohiro; Korenwein, Viatcheslav; Nichterlein, André; Niedermeier, Rolf; Zschoche, Philipp
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
ACM Journal of Experimental Algorithmics, 24 :1–30
2021
Publisher: ACM
Ulitzsch, Esther; He, Qiwei; Ulitzsch, Vincent; Nichterlein, André; Molter, Hendrik; Niedermeier, Rolf; Pohl, Steffi
Combining Clickstream Analyses and Graph-Modeled Data Clustering for Identifying Common Response Processes
Psychometrika :1–25
2021
Publisher: Springer

2020

Bentert, Matthias; Dittmann, Alexander; Kellerhals, Leon; Nichterlein, André; Niedermeier, Rolf
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Journal of Graph Algorithms and Applications, 24 (3) :483–522
2020
Bentert, Matthias; Himmel, Anne-Sophie; Nichterlein, André; Niedermeier, Rolf
Efficient computation of optimal temporal walks under waiting-time constraints
Applied Network Science, 5 (73) :1–26
2020
Mertzios, George B.; Nichterlein, André; Niedermeier, Rolf
The Power of Linear-Time Data Reduction for Maximum Matching
Algorithmica, 82 :3521–3565
2020
Publisher: Springer

2019

Contribution to Proceedings
Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André
Parameterized Complexity of Min-Power Asymmetric Connectivity
, Proceedings of the 30th International Workshop (IWOCA '19)Volume11638fromLecture Notes in Computer Science, Page 85–96
Publisher: Springer
2019
ISBN
978-3-030-25004-1
Bentert, Matthias; Nichterlein, André
Parameterized Complexity of Diameter
, Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC '19)Volume11485fromLecture Notes in Computer Science, Page 50–61
Publisher: Springer
2019
Himmel, Anne-Sophie; Bentert, Matthias; Nichterlein, André; Niedermeier, Rolf
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
, Proceedings of the 8th International Conference on Complex Networks and their ApplicationsVolume882fromSCI, Page 494–506
Publisher: Springer
2019
Articles
Bentert, Matthias; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf
Parameterized aspects of triangle enumeration
Journal of Computer and System Sciences, 103 :61 - 77
2019
Fluschnik, Till; Komusiewicz, Christian; Mertzios, George B.; Nichterlein, André; Niedermeier, Rolf; Talmon, Nimrod
When Can Graph Hyperbolicity be Computed in Linear Time?
Algorithmica, 81 (5) :2016–2045
2019
ISSN: 1432-0541
Bazgan, Cristina; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf; Stahlberg, Maximilian
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
Networks, 73 (1) :23–37
2019