Algorithmik und Komplexitätstheorie

Dr.

André Nichterlein

Dauer-Wiss. Mitarbeiter_in

andre.nichterlein@tu-berlin.de

+49 30 314-19001820

Einrichtung Algorithmik und Komplexitätstheorie
Sekretariat TEL 5-1
Raum TEL 509D
SprechstundenDienstag 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

Publikationen

2023

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

2022

Artikel
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.
Beiträge zu Verhandlungen
H. Schulz, A. Nichterlein, R. Niedermeier and C. Weyand, "Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time" in Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 25:1–25:14.
N. Boehmer, R. Bredereck and A. Nichterlein, "Combating Collusion Rings is Hard but Possible" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 4843–4850.
T. Koana, C. Komusiewicz, A. Nichterlein and F. Sommer, "Covering Many (Or Few) Edges with k Vertices in Sparse Graphs" in Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 42:1–42:18.
A. Figiel, V. Froese, A. Nichterlein and R. Niedermeier, "There and Back Again: On Applying Data Reduction Rules by Undoing Others" in Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 53:1–53:15.

2021

M. Bentert, A. Nichterlein, M. Renken and P. Zschoche, "Using a Geometric Lens to Find $k$ Disjoint Shortest Paths" in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. pp. 26:1–26:14.
M. Rymar, H. Molter, A. Nichterlein and R. Niedermeier, "Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality" in Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '21), Springer, 2021. pp. 219–231.
A. Figiel, A. Himmel, A. Nichterlein and R. Niedermeier, "On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering" in Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC '21), Springer, 2021. pp. 216–230.
Artikel
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, 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.
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.
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.
E. Ulitzsch, Q. He, V. Ulitzsch, A. Nichterlein, H. Molter, R. Niedermeier and S. Pohl, "Combining Clickstream Analyses and Graph-Modeled Data Clustering for Identifying Common Response Processes" , Psychometrika, pp. 1–25, 2021. Springer.

2020

M. Bentert, A. Dittmann, L. Kellerhals, A. Nichterlein and R. Niedermeier, "An Adaptive Version of Brandes' Algorithm for Betweenness Centrality" , Journal of Graph Algorithms and Applications, vol. 24, no. 3, pp. 483–522, 2020.
M. Bentert, A. Himmel, A. Nichterlein and R. Niedermeier, "Efficient computation of optimal temporal walks under waiting-time constraints" , Applied Network Science, vol. 5, no. 73, pp. 1–26, 2020.
G. B. Mertzios, A. Nichterlein and R. Niedermeier, "The Power of Linear-Time Data Reduction for Maximum Matching" , Algorithmica, vol. 82, pp. 3521–3565, 2020. Springer.

2019

Beiträge zu Verhandlungen
M. Bentert, R. Haag, C. Hofer, T. Koana and A. Nichterlein, "Parameterized Complexity of Min-Power Asymmetric Connectivity" in Proceedings of the 30th International Workshop (IWOCA '19), Springer, 2019. pp. 85–96.
ISBN
978-3-030-25004-1
M. Bentert and A. Nichterlein, "Parameterized Complexity of Diameter" in Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC '19), Springer, 2019. pp. 50–61.
A. Himmel, M. Bentert, A. Nichterlein and R. Niedermeier, "Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints" in Proceedings of the 8th International Conference on Complex Networks and their Applications, Springer, 2019. pp. 494–506.
Artikel
M. Bentert, T. Fluschnik, A. Nichterlein and R. Niedermeier, "Parameterized aspects of triangle enumeration" , Journal of Computer and System Sciences, vol. 103, pp. 61 - 77, 2019.
T. Fluschnik, C. Komusiewicz, G. B. Mertzios, A. Nichterlein, R. Niedermeier and N. Talmon, "When Can Graph Hyperbolicity be Computed in Linear Time?" , Algorithmica, vol. 81, no. 5, pp. 2016–2045, 2019.
C. Bazgan, T. Fluschnik, A. Nichterlein, R. Niedermeier and M. Stahlberg, "A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths" , Networks, vol. 73, no. 1, pp. 23–37, 2019.
C. Komusiewicz, A. Nichterlein, R. Niedermeier and M. Picker, "Exact Algorithms for Finding Well-Connected 2-Clubs in Sparse Real-World Graphs: Theory and Experiments" , European Journal of Operational Research, vol. 275, no. 3, pp. 846–864, 2019.
R. Bredereck, V. Froese, M. Koseler, M. G. Millani, A. Nichterlein and R. Niedermeier, "A Parameterized Algorithmics Framework for Digraph Degree Sequence Completion Problems" , Algorithmica, vol. 81, no. 4, pp. 1584–1614, 2019.

2018

G. B. Mertzios, A. Nichterlein and R. Niedermeier, "A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs" , SIAM Journal on Discrete Mathematics, vol. 32, no. 4, pp. 2820-2835, 2018.
T. Fluschnik, D. Hermelin, A. Nichterlein and R. Niedermeier, "Fractals for Kernelization Lower Bounds" , SIAM Journal on Discrete Mathematics, vol. 32, no. 1, pp. 656–681, 2018.
Beiträge zu Verhandlungen
M. Bentert, A. Dittmann, L. Kellerhals, A. Nichterlein and R. Niedermeier, "An Adaptive Version of Brandes' Algorithm for Betweenness Centrality" in Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. pp. 36:1–36:13.
V. Korenwein, A. Nichterlein, R. Niedermeier and P. Zschoche, "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments" in Proceedings of the 26th Annual European Symposium on Algorithms (ESA '18), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. pp. 53:1–53:13.
T. Fluschnik, G. B. Mertzios and A. Nichterlein, "Kernelization Lower Bounds for Finding Constant-Size Subgraphs" in Proceedings of the 14th Conference on Computability in Europe (CiE '18), Springer International Publishing, 2018. pp. 183–193.
J. Luo, H. Molter, A. Nichterlein and R. Niedermeier, "Parameterized Dynamic Cluster Editing" in Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '18), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. pp. 46:1–46:15.

2017

Artikel
V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, "Finding Points in General Position" , International Journal of Computational Geometry & Applications, vol. 27, no. 4, pp. 277–296, 2017.
R. Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Hüffner, A. Nichterlein and O. Suchý, "Fixed-parameter algorithms for DAG Partitioning" , Discrete Applied Mathematics, vol. 220, pp. 134–160, 2017.
Beiträge zu Verhandlungen
R. Bredereck, V. Froese, M. Koseler, M. G. Millani, A. Nichterlein and R. Niedermeier, "A Parameterized Algorithmics Framework for Digraph Degree Sequence Completion Problems" in Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC '16), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. pp. 10:1–10:14.
M. Bentert, R. Bevern, A. Nichterlein and R. Niedermeier, "Parameterized algorithms for power-efficient connected symmetric wireless sensor networks" in Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS '17), Springer International Publishing, 2017. pp. 26–40.
M. Bentert, T. Fluschnik, A. Nichterlein and R. Niedermeier, "Parameterized Aspects of Triangle Enumeration" in Proceedings of the 21st Symposium on Fundamentals of Computation Theory (FCT '17), Springer International Publishing, 2017. pp. 96–110.
G. B. Mertzios, A. Nichterlein and R. Niedermeier, "The Power of Linear-Time Data Reduction for Maximum Matching" in Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS '17), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. pp. 46:1–46:14.
T. Fluschnik, C. Komusiewicz, G. B. Mertzios, A. Nichterlein, R. Niedermeier and N. Talmon, "When can Graph Hyperbolicity be computed in Linear Time?" in Proceedings of the 15th Workshop on Algorithms and Data Structures (WADS '17), Springer International Publishing, 2017. pp. 397–408.

2016

V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, "Finding Points in General Position" in Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG '16), 2016. pp. 7–14.
T. Fluschnik, D. Hermelin, A. Nichterlein and R. Niedermeier, "Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems" in Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP '16), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. pp. 25:1–25:14.
Artikel
R. Bredereck, J. Chen, A. Nichterlein, P. Faliszewski and R. Niedermeier, "Prices Matter for the Parameterized Complexity of Shift Bribery" , Information and Computation, vol. 251, pp. 140–164, 2016.
C. Bazgan, R. Bredereck, S. Hartung, A. Nichterlein and G. J. Woeginger, "Finding large degree-anonymous subgraphs is hard" , Theoretical Computer Science, vol. 622, pp. 90–110, 2016.
V. Froese, A. Nichterlein and R. Niedermeier, "Win-Win Kernelization for Degree Sequence Completion Problems" , Journal of Computer and System Sciences, vol. 82, no. 6, pp. 1100–1111, 2016.

2015

S. Hartung, A. Nichterlein, R. Niedermeier and O. Suchý, "A Refined Complexity Analysis of Degree Anonymization on Graphs" , Information and Computation, vol. 243, pp. 249–262, 2015.
S. Hartung and A. Nichterlein, "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs" , SIAM Journal on Discrete Mathematics, vol. 29, no. 4, pp. 1931-1960, 2015.
S. Hartung, C. Komusiewicz, A. Nichterlein and O. Suchý, "On structural parameterizations for the 2-club problem" , Discrete Applied Mathematics, vol. 185, pp. 79-92, 2015.
S. Hartung, C. Komusiewicz and A. Nichterlein, "Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs" , Journal of Graph Algorithms and Applications, vol. 19, no. 1, pp. 155–190, 2015.
R. Bredereck, V. Froese, S. Hartung, A. Nichterlein, R. Niedermeier and N. Talmon, "The Complexity of Degree Anonymization by Vertex Addition" , Theoretical Computer Science, vol. 607, no. 1, pp. 16–34, 2015. Elsevier.
R. Bredereck, T. Köhler, A. Nichterlein, R. Niedermeier and G. Philip, "Using Patterns to Form Homogeneous Teams" , Algorithmica, vol. 71, no. 2, pp. 517-538, 2015. Springer.
Beiträge zu Verhandlungen
C. Bazgan, A. Nichterlein and R. Niedermeier, "A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths" in Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC'15), Springer, 2015. pp. 47–60.
F. Hüffner, C. Komusiewicz and A. Nichterlein, "Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes" in Proceedings of the Algorithms and Data Structures Symposium (WADS'15), Springer, 2015. pp. 410–421.
C. Komusiewicz, A. Nichterlein and R. Niedermeier, "Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics" in Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG '15), Springer, 2015.

2014

PhD-Thesis
A. Nichterlein, "Degree-Constrained Editing of Small-Degree Graphs", PhD Thesis, TU Berlin, Dez. 2014.
Beiträge zu Verhandlungen
C. Bazgan and A. Nichterlein, "Parameterized Inapproximability of Degree Anonymization" in Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC '14), Springer, 2014. pp. 75–84.
V. Froese, A. Nichterlein and R. Niedermeier, "Win-Win Kernelization for Degree Sequence Completion Problems" in Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '14), Springer, 2014. pp. 194–205.
R. Bredereck, V. Froese, S. Hartung, A. Nichterlein, R. Niedermeier and N. Talmon, "The Complexity of Degree Anonymization by Vertex Addition" in Proceedings of the 10th International Conference on Algorithmic Aspects of Information and Management (AAIM '14), Springer, 2014. pp. 44–55.
C. Bazgan, M. Chopin, A. Nichterlein and F. Sikora, "Parameterized Inapproximability of Target Set Selection and Generalizations" in Proceedings of the 10th International Conference on Computability in Europe (CiE' 14), Springer, 2014. pp. 11–20.
R. Bredereck, J. Chen, A. Nichterlein, P. Faliszewski and R. Niedermeier, "Prices Matter for the Parameterized Complexity of Shift Bribery" in Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI '14), 2014. pp. 552–558.
S. Hartung, C. Hoffmann and A. Nichterlein, "Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks" in Proceedings of the 13th Symposium on Experimental Algorithms (SEA' 14), Springer, 2014. pp. 376–387.
Artikel
R. Bredereck, A. Nichterlein, R. Niedermeier and G. Philip, "The Effect of Homogeneity on the Computational Complexity of Combinatorial Data Anonymization" , Data Mining and Knowledge Discovery, vol. 28, no. 1, pp. 65–91, 2014. Springer.
C. Bazgan, M. Chopin, A. Nichterlein and F. Sikora, "Parameterized Inapproximability of Target Set Selection and Generalizations" , Computability, vol. 3, no. 2, pp. 135–145, 2014.
C. Bazgan, M. Chopin, A. Nichterlein and F. Sikora, "Parameterized approximability of maximizing the spread of influence in networks" , Journal of Discrete Algorithms, vol. 27, pp. 54-65, 2014.
R. Bevern, S. Hartung, A. Nichterlein and M. Sorge, "Constant-factor approximations for Capacitated Arc Routing without triangle inequality" , Operations Research Letters, vol. 4, no. 4, pp. 290–292, 2014.
M. Chopin, A. Nichterlein, R. Niedermeier and M. Weller, "Constant Thresholds Can Make Target Set Selection Tractable" , Theory of Computing Systems, vol. 55, no. 1, pp. 61–83, 2014. Springer.

2013

Beiträge zu Verhandlungen
R. Bredereck, S. Hartung, A. Nichterlein and G. Woeginger, "The complexity of finding a large subgraph under anonymity constraints" in Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13), Springer, 2013. pp. 152–162.
R. Bredereck, A. Nichterlein and R. Niedermeier, "Pattern-Guided k-Anonymity" in Proceedings of the Joint Conference of the 7th International Frontiers of Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM '13), Springer, 2013. pp. 350-361.
R. Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Hüffner, A. Nichterlein and O. Suchý, "Parameterized Complexity of DAG Partitioning" in Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC '13), Springer, 2013. pp. 49-60.
C. Bazgan, M. Chopin, A. Nichterlein and F. Sikora, "Parameterized Approximability of Maximizing the Spread of Influence in Networks" in Proceedings of the 9th Annual International Computing and Combinatorics Conference (COCOON'13), Springer, 2013. pp. 543-554.
S. Hartung and A. Nichterlein, "On the Parameterized and Approximation Hardness of Metric Dimension" in Proceedings of the 28th IEEE Conference on Computational Complexity (CCC '13), IEEE, 2013. pp. 266-276.
S. Hartung, C. Komusiewicz and A. Nichterlein, "On Structural Parameterizations for the 2-Club Problem" in Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '13), Springer, 2013. pp. 233-243.
S. Hartung, A. Nichterlein, R. Niedermeier and O. Suchý, "A Refined Complexity Analysis of Degree Anonymization on Graphs" in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13), Springer, 2013. pp. 594-606.
Artikel
R. Bredereck, A. Nichterlein and R. Niedermeier, "Pattern-Guided k-Anonymity" , Algorithms, vol. 6, no. 4, pp. 678–701, 2013.
A. Nichterlein, R. Niedermeier, J. Uhlmann and M. Weller, "On tractable cases of Target Set Selection" , Social Network Analysis and Mining, vol. 3, no. 2, pp. 233-256, 2013. Springer.

2012

Beiträge zu Verhandlungen
M. Chopin, A. Nichterlein, R. Niedermeier and M. Weller, "Constant Thresholds Can Make Target Set Selection Tractable" in Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg '12), 2012. pp. 120-133.
S. Hartung and A. Nichterlein, "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs" in Proceedings of the 8th International Conference on Computability in Europe 2012 (CiE 2012), Springer, 2012. pp. 283-292.
S. Hartung, C. Komusiewicz and A. Nichterlein, "Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs" in Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC'12), Springer, 2012. pp. 231-241.

2011

Artikel
A. Nichterlein, M. Dom and R. Niedermeier, "Aspects of a Multivariate Complexity Analysis for Rectangle Tiling" , Operation Research Letters, vol. 39, no. 5, pp. 346-351, 2011. Elsevier.
Beiträge zu Verhandlungen
R. Bredereck, A. Nichterlein, R. Niedermeier and G. Philip, "Pattern-Guided Data Anonymization and Clustering" in Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS '11), Springer, 2011. pp. 182-193.
R. Bredereck, A. Nichterlein, R. Niedermeier and G. Philip, "The Effect of Homogeneity on the Complexity of $k$-Anonymity" in Proceedings of the 18th International Symposium on Fundamentals of Computation Theory (FCT '11), Springer, 2011. pp. 53-64.

2010

A. Nichterlein, R. Niedermeier, J. Uhlmann and M. Weller, "On Tractable Cases of Target Set Selection" in Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC '10), Part I, Springer, 2010. pp. 378–389.