Sie sind hier

### Inhalt des Dokuments

Dr. André Nichterlein, Postdoc
Technische Universität Berlin
Fakultät IV
Sekr. TEL 5-1
Ernst-Reuter-Platz 7
10587 Berlin

Room:
TEL 509A
Phone:
+49(0)30-314 73137
E-Mail:
andre.nichterlein 'at' tu-berlin.de
Research Interests:
parameterized algorithms
graph modification problems
dynamics in social networks
(parameterized) approximation
Office hour
Thursday 17:30-18:30

## 2017

 René van Bevern and Robert Bredereck and Morgan Chopin and Sepp Hartung and Falk Hüffner and André Nichterlein and Ondřej Suchý. Fixed-parameter algorithms for DAG Partitioning. Discrete Applied Mathematics, 1–27, 2017. In press. Bibtex entry
 Vincent Froese and Iyad Kanj and André Nichterlein and Rolf Niedermeier. Finding Points in General Position. International Journal of Computational Geometry & Applications, 2017. Accepted for publication. Bibtex entry Link to publication

## 2016

 Cristina Bazgan and Robert Bredereck and Sepp Hartung and André Nichterlein and Gerhard J. Woeginger. Finding large degree-anonymous subgraphs is hard. Theoretical Computer Science, 622:90–110, 2016. Bibtex entry
 Vincent Froese and André Nichterlein and Rolf Niedermeier. Win-Win Kernelization for Degree Sequence Completion Problems. Journal of Computer and System Sciences, 82(6):1100–1111, 2016. Bibtex entry
 Robert Bredereck and Jiehua Chen and André Nichterlein and Piotr Faliszewski and Rolf Niedermeier. Prices Matter for the Parameterized Complexity of Shift Bribery. Information and Computation, 251:140–164, 2016. Bibtex entry Link to original publication

## 2015

 Robert Bredereck and Vincent Froese and Sepp Hartung and André Nichterlein and Rolf Niedermeier and Nimrod Talmon. The Complexity of Degree Anonymization by Vertex Addition. Theoretical Computer Science, 607(Part 1):16–34, Elsevier, 2015. Bibtex entry
 Sepp Hartung and Christian Komusiewicz and André Nichterlein and Ondrej Suchý. On structural parameterizations for the 2-club problem. Discrete Applied Mathematics, 185:79-92, 2015. Bibtex entry
 Sepp Hartung and Christian Komusiewicz and André Nichterlein. Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs. Journal of Graph Algorithms and Applications, 19(1):155–190, 2015. Bibtex entry
 Robert Bredereck and Thomas Köhler and André Nichterlein and Rolf Niedermeier and Geevarghese Philip. Using Patterns to Form Homogeneous Teams. Algorithmica, 71(2):517-538, Springer, 2015. Bibtex entry
 Sepp Hartung and André Nichterlein and Rolf Niedermeier and Ondrej Suchý. A Refined Complexity Analysis of Degree Anonymization on Graphs. Information and Computation, 243:249–262, 2015. Bibtex entry
 Sepp Hartung and André Nichterlein. NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs. SIAM Journal on Discrete Mathematics, 29(4):1931-1960, 2015. Bibtex entry

## 2014

 Robert Bredereck and André Nichterlein and Rolf Niedermeier and Geevarghese Philip. The Effect of Homogeneity on the Computational Complexity of Combinatorial Data Anonymization. Data Mining and Knowledge Discovery, 28(1):65–91, Springer, 2014. Bibtex entry
 René van Bevern and Sepp Hartung and André Nichterlein and Manuel Sorge. Constant-factor approximations for {Capacitated Arc Routing} without triangle inequality. Operations Research Letters, 4(4):290–292, 2014. Bibtex entry
 Morgan Chopin and André Nichterlein and Rolf Niedermeier and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. Theory of Computing Systems, 55(1):61–83, Springer, 2014. Bibtex entry
 Cristina Bazgan and Morgan Chopin and André Nichterlein and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. Journal of Discrete Algorithms, 27:54-65, 2014. Bibtex entry
 Cristina Bazgan and Morgan Chopin and André Nichterlein and Florian Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. Computability, 3(2):135–145, 2014. Bibtex entry

## 2013

 André Nichterlein and Rolf Niedermeier and Johannes Uhlmann and Mathias Weller. On tractable cases of Target Set Selection. Social Network Analysis and Mining, 3(2):233-256, Springer, 2013. Bibtex entry
 Robert Bredereck and André Nichterlein and Rolf Niedermeier. Pattern-Guided k-Anonymity. Algorithms, 6(4):678–701, 2013. Bibtex entry

## 2011

 André Nichterlein and Michael Dom and Rolf Niedermeier. Aspects of a Multivariate Complexity Analysis for Rectangle Tiling. Operation Research Letters, 39(5):346-351, Elsevier, 2011. Bibtex entry

## 2017

 Robert Bredereck and Vincent Froese and Marcel Koseler and Marcelo Garlet Millani and André Nichterlein and Rolf 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), pages 10:1–10:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Bibtex entry
 Till Fluschnik and Christian Komusiewicz and George B. Mertzios and André Nichterlein and Rolf Niedermeier and Nimrod Talmon. When can Graph Hyperbolicity be computed in Linear Time?. In Proceedings of the 15th Workshop on Algorithms and Data Structures (WADS '17), pages 397–408. Springer International Publishing, 2017. Bibtex entry Link to publication
 Matthias Bentert and Till Fluschnik and André Nichterlein and Rolf Niedermeier. Parameterized Aspects of Triangle Enumeration. In Proceedings of the 21st Symposium on Fundamentals of Computation Theory (FCT '17), 2017. Accepted for publication. Bibtex entry Link to publication

## 2016

 Till Fluschnik and Danny Hermelin and André Nichterlein and Rolf 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), pages 25:1–25:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Bibtex entry
 Vincent Froese and Iyad Kanj and André Nichterlein and Rolf Niedermeier. Finding Points in General Position. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG '16), pages 7–14. 2016. Bibtex entry

## 2015

 Falk Hüffner and Christian Komusiewicz and André Nichterlein. Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes. In Proceedings of the Algorithms and Data Structures Symposium (WADS'15), pages 410–421. Springer, 2015. Bibtex entry
 Cristina Bazgan and André Nichterlein and Rolf 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), pages 47–60. Springer, 2015. Bibtex entry
 Christian Komusiewicz and André Nichterlein and Rolf 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. Bibtex entry Link to publication

## 2014

 Vincent Froese and André Nichterlein and Rolf Niedermeier. Win-Win Kernelization for Degree Sequence Completion Problems. In Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '14), pages 194–205. Springer, 2014. Bibtex entry
 Robert Bredereck and Jiehua Chen and André Nichterlein and Piotr Faliszewski and Rolf Niedermeier. Prices Matter for the Parameterized Complexity of Shift Bribery. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI '14), pages 552–558. 2014. Bibtex entry
 Cristina Bazgan and André Nichterlein. Parameterized Inapproximability of Degree Anonymization. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC '14), pages 75–84. Springer, 2014. Bibtex entry
 Sepp Hartung and Clemens Hoffmann and André Nichterlein. Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks. In Proceedings of the 13th Symposium on Experimental Algorithms (SEA' 14), pages 376–387. Springer, 2014. Bibtex entry
 Cristina Bazgan and Morgan Chopin and André Nichterlein and Florian Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. In Proceedings of the 10th International Conference on Computability in Europe (CiE' 14), pages 11–20. Springer, 2014. Bibtex entry
 Robert Bredereck and Vincent Froese and Sepp Hartung and André Nichterlein and Rolf Niedermeier and Nimrod 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), pages 44–55. Springer, 2014. Bibtex entry

## 2013

 Cristina Bazgan and Morgan Chopin and André Nichterlein and Florian Sikora. Parameterized Approximability of Maximizing the Spread of Influence in Networks. In Proceedings of the 9th Annual International Computing and Combinatorics Conference (COCOON'13), pages 543-554. Springer, 2013. Bibtex entry
 Sepp Hartung and André Nichterlein and Rolf Niedermeier and Ondrej Suchý. A Refined Complexity Analysis of Degree Anonymization on Graphs. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13), pages 594-606. Springer, 2013. Bibtex entry
 Robert Bredereck and André Nichterlein and Rolf 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), pages 350-361. Springer, 2013. Bibtex entry
 Sepp Hartung and Christian Komusiewicz and André 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), pages 233-243. Springer, 2013. Bibtex entry
 Sepp Hartung and André Nichterlein. On the Parameterized and Approximation Hardness of Metric Dimension. In Proceedings of the 28th IEEE Conference on Computational Complexity (CCC '13), pages 266-276. IEEE, 2013. Bibtex entry
 René van Bevern and Robert Bredereck and Morgan Chopin and Sepp Hartung and Falk Hüffner and André Nichterlein and Ondrej Suchý. Parameterized Complexity of DAG Partitioning. In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC '13), pages 49-60. Springer, 2013. Bibtex entry
 Robert Bredereck and Sepp Hartung and André Nichterlein and Gerhard Woeginger. The complexity of finding a large subgraph under anonymity constraints. In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13), pages 152–162. Springer, 2013. Bibtex entry

## 2012

 Sepp Hartung and Christian Komusiewicz and André Nichterlein. Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs. In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC'12), pages 231-241. Springer, 2012. Bibtex entry
 Sepp Hartung and André 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), pages 283-292. Springer, 2012. Bibtex entry
 Morgan Chopin and André Nichterlein and Rolf Niedermeier and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. In Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg '12), pages 120-133. 2012. Bibtex entry

## 2011

 Robert Bredereck and André Nichterlein and Rolf Niedermeier and Geevarghese 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), pages 53-64. Springer, 2011. Bibtex entry
 Robert Bredereck and André Nichterlein and Rolf Niedermeier and Geevarghese Philip. Pattern-Guided Data Anonymization and Clustering. In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS '11), pages 182-193. Springer, 2011. Bibtex entry

## 2010

 André Nichterlein and Rolf Niedermeier and Johannes Uhlmann and Mathias Weller. On Tractable Cases of Target Set Selection. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC '10), Part I, pages 378–389. Springer, 2010. Bibtex entry

To top

# PhD Thesis

## 2014

 André Nichterlein. Degree-Constrained Editing of Small-Degree Graphs. TU Berlin, December, 2014. Published by Universitätsverlag der TU Berlin. Bibtex entry Link to PDF