direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

From February 1, 2016 until January 31, 2017 I am in Durham with George Mertzios (funded by DAAD).

Dr. André Nichterlein, Postdoc
Address:
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
Tuesday 16-17

Journal Publications

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 Link to publication
Link to original publication
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 Link to publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication
Robert Bredereck and André Nichterlein and Rolf Niedermeier.
Pattern-Guided k-Anonymity.
Algorithms, 6(4):678–701, 2013.
Bibtex entry Link to publication
Link to original publication

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 Link to publication
Link to original publication

Conference Publications

2016

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), 2016. Accepted for publication.
Bibtex entry Link to publication
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), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Accepted for publication.
Bibtex entry Link to publication
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), 2016. Accepted for publication.
Bibtex entry Link to publication

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication
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 Link to publication
Link to original publication

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 Link to publication
Link to original publication

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

Zusatzinformationen / Extras