direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Prof. Dr. Rolf Niedermeier

Contact

Bild
Lupe

Snail mail:
Rolf Niedermeier
Technische Universität Berlin
Fakultät IV - Elektrotechnik und Informatik
Sekr. TEL 5-1
Ernst-Reuter-Platz 7
D-10587 Berlin

Phone: +49 30 314 21759
Room: Ernst-Reuter-Platz 7, Room 509c
E-Mail: rolf.niedermeier at tu-berlin.de
Office hour: Thursday 17:30-18:30

Secretary

Christlinde Thielcke
E-Mail: christlinde.thielcke at tu-berlin.de
Phone: +49 30 314 73510
Fax: +49 30 314 23516

Research interests

Parameterized Computational Complexity, NP-Hard Problems, Exact Algorithms, Graph Algorithms, Complexity of Voting Problems, Biological and Social Network Analysis.

Current and Upcoming Community Service

Short Bio

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

Teaching

Courses on Foundations of Theoretical Computer Science, Foundations of Algorithmics, Computational Complexity, Parameterized Algorithmics, Randomized Algorithms, ...

Conference Publications 2014

René van Bevern and Robert Bredereck and Laurent Bulteau and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Gerhard J. Woeginger.
Star Partitions of Perfect Graphs.
In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP' 14), pages 174–185. Springer, 2014.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Robert Bredereck and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Gerhard J. Woeginger.
Network-based dissolution.
In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), pages 69–80. 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 International Conference on Algorithmic Aspects of Information and Management (AAIM' 2014), pages 44–55. 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 Conference on Artificial Intelligence (AAAI '14), pages 552–558. 2014.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Vincent Froese and Sepp Hartung and Rolf Niedermeier.
Co-Clustering Under the Maximum Norm.
In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC' 2014), pages 298–309. Springer, 2014.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon.
Combinatorial Voter Control in Elections.
In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), 2014. Accepted for publication.
Bibtex entry Link to 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
Falk Hüffner and Christian Komusiewicz and Rolf Niedermeier and Martin Rötzschke.
The Parameterized Complexity of the Rainbow Subgraph Problem.
In Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '14), pages 287–298. Springer, 2014.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2014

Nadja Betzler and Robert Bredereck and Rolf Niedermeier.
Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation.
Autonomous Agents and Multi-Agent Systems, 28(5):721–748, Springer, 2014.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Hans Bodlaender and Robert Bredereck and Rolf Niedermeier and Johannes Uhlmann.
On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion.
Algorithmica, 715-738, Springer, 2014.
Bibtex entry Link to publication
Link to original publication
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
Laurent Bulteau and Falk Hüffner and Christian Komusiewicz and Adrian Liebtrau and Rolf Niedermeier.
Multivariate Algorithmics for NP-Hard String Problems.
Bulletin of the EATCS, 114:31-73, 2014.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge and Ondrej Suchý and Mathias Weller.
Polynomial-Time Data Reduction for the Subset Interconnection Design Problem.
SIAM Journal on Discrete Mathematics, 2014. Accepted for publication.
Bibtex entry Link to 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
Sepp Hartung and André Nichterlein and Rolf Niedermeier and Ondrej Suchý.
A Refined Complexity Analysis of Degree Anonymization on Graphs.
Information and Computation, 2014. Accepted for publication.
Bibtex entry Link to publication
Falk Hüffner and Christian Komusiewicz and Adrian Liebtrau and Rolf Niedermeier.
Partitioning biological networks into highly connected clusters with maximum edge coverage.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(3):455-467, 2014.
Bibtex entry Link to publication
Link to original publication
Manuel Sorge and Hannes Moser and Rolf Niedermeier and Mathias Weller.
Exploiting a Hypergraph Model for Finding Golomb Rulers.
Acta Informatica, 51:449–471, Springer, 2014.
Bibtex entry Link to publication
Link to original publication

Book Chapters 2014

René van Bevern and Rolf Niedermeier and Manuel Sorge and Mathias Weller.
Complexity of Arc Routing Problems.
In Arc Routing: Problems, Methods, and Applications, SIAM, 2014. In press
Bibtex entry Link to publication

Conference Publications 2013

Noga Alon and Robert Bredereck and Jiehua Chen and Stefan Kratsch and Rolf Niedermeier and Gerhard J. Woeginger.
How to Put Through Your Agenda in Collective Binary Decisions.
In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT '13), pages 30-44. 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
Robert Bredereck and Jiehua Chen and Sepp Hartung and Christian Komusiewicz and Rolf Niedermeier and Ondrej Suchý.
On Explaining Integer Vectors by Few Homogenous Segments.
In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS '13), pages 207-218. 2013.
Bibtex entry Link to publication
Sharon Bruckner and Falk Hüffner and Christian Komusiewicz and Rolf Niedermeier.
Evaluation of ILP-based Approaches for Partitioning into Colorful Components.
In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA '13), pages 176-187. Springer, 2013.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge and Ondrej Suchý and Mathias Weller.
Effective and Efficient Data Reduction for the Subset Interconnection Design Problem.
In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13), pages 361–371. 2013.
Bibtex entry Link to publication
Link to original publication
Vincent Froese and René van Bevern and Rolf Niedermeier and Manuel Sorge.
A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems.
In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS '13), pages 445–456. 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
Falk Hüffner and Christian Komusiewicz and Adrian Liebtrau and Rolf Niedermeier.
Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.
In Proceedings of the 9th International Symposium on Bioinformatics Research and Applications (ISBRA '13), pages 99-111. Springer, 2013.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2013

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
Robert Bredereck and Thomas Köhler and André Nichterlein and Rolf Niedermeier and Geevarghese Philip.
Using Patterns to Form Homogeneous Teams.
Algorithmica, Springer, 2013. Online Available.
Bibtex entry Link to publication
Link to original publication
Frederic Dorn and Hannes Moser and Rolf Niedermeier and Mathias Weller.
Efficient Algorithms for Eulerian Extension and Rural Postman.
SIAM Journal on Discrete Mathematics, 27(1):75–94, SIAM, 2013.
Bibtex entry Link to publication
Link to original publication
Hartmut Ehrig and Claudia Ermel and Falk Hüffner and Rolf Niedermeier and Olga Runge.
Confluence in data reduction: bridging graph transformation and kernelization.
Computability, 2(1):31-49, 2013.
Bibtex entry Link to publication
Link to original publication
Sepp Hartung and Rolf Niedermeier.
Incremental List Coloring of Graphs, Parameterized by Conservation.
Theoretical Computer Science, 494:86-98, 2013.
Bibtex entry Link to publication
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

Conference Publications 2012

René van Bevern and Matthias Mnich and Rolf Niedermeier and Mathias Weller.
Interval Scheduling and Colorful Independent Sets.
In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC '12), pages 247–256. 2012.
Bibtex entry Link to publication
Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondřej Suchý.
A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
In Proceedings of the 26th Conference on Artificial Intelligence (AAAI '12), pages 1292-1298. AAAI Press, 2012.
Bibtex entry Link to publication
Link to original publication
Sharon Bruckner and Falk Hüffner and Christian Komusiewicz and Rolf Niedermeier and Sven Thiel and Johannes Uhlmann.
Partitioning into Colorful Components by Minimum Edge Deletions.
In Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM '12), pages 56-69. 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
Hartmut Ehrig and Claudia Ermel and Falk Hüffner and Rolf Niedermeier and Olga Runge.
Confluence in data reduction: bridging graph transformation and kernelization.
In Proceedings of the 8th Conference on Computability in Europe (CiE '12), 2012.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and Rolf Niedermeier.
New Races in Parameterized Algorithmics.
In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS '12), pages 19-30. Springer, 2012.
Bibtex entry Link to publication
Link to original publication
Manuel Sorge and Hannes Moser and Rolf Niedermeier and Mathias Weller.
Exploiting a Hypergraph Model for Finding Golomb Rulers.
In Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO'12), pages 368-379. Springer, 2012.
Bibtex entry Link to publication
Link to original publication

Book Chapters 2012

Nadja Betzler and Robert Bredereck and Jiehua Chen and Rolf Niedermeier.
Studies in Computational Aspects of Voting - A Parameterized Complexity Perspective.
In The Multivariate Algorithmic Revolution and Beyond, pages 318-363. Springer, 2012.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2012

Nadja Betzler and Robert Bredereck and Rolf Niedermeier and Johannes Uhlmann.
On Bounded-Degree Vertex Deletion Parameterized by Treewidth.
Discrete Applied Mathematics, 160(1–2):53–60, Elsevier, 2012.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Hannes Moser and Rolf Niedermeier.
Approximation and Tidying-A Problem Kernel for s-Plex Cluster Vertex Deletion.
Algorithmica, 62(3):930–950, Springer, 2012.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Sepp Hartung and Rolf Niedermeier and Ondrej Suchý.
The Parameterized Complexity of Local Search for TSP, More Refined.
Algorithmica, 67(1):89-110, Springer, 2013.
Bibtex entry Link to publication
Link to original publication
Hannes Moser and Rolf Niedermeier and Manuel Sorge.
Exact combinatorial algorithms and experiments for finding maximum $k$-plexes.
Journal of Combinatorial Optimization, 24:347–373, Springer, 2012.
Bibtex entry Link to publication
Link to original publication
Alexander Schäfer and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Parameterized Computational Complexity of Finding Small-Diameter Subgraphs.
Optimization Letters, 6(5):883-891, Springer, 2012.
Bibtex entry Link to publication
Link to original publication
Manuel Sorge and René van Bevern and Rolf Niedermeier and Mathias Weller.
A New View on Rural Postman Based on Eulerian Extension and Matching.
Journal of Discrete Algorithms, 16:12–33, Elsevier, 2012.
Bibtex entry Link to publication
Link to original publication
Mathias Weller and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
On making directed graphs transitive.
Journal of Computer and System Sciences, 78(2):559–574, Elsevier, 2012.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2011

Nadja Betzler and Robert Bredereck and Rolf Niedermeier and Johannes Uhlmann.
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion.
In Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '11), pages 123–134. Springer, 2011.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Rolf Niedermeier and Gerhard Woeginger.
Unweighted Coalitional Manipulation Under the Borda Rule is NP-Hard.
In Proceedings of the 22th International Joint Conference on Artificial Intelligence (IJCAI '11), pages 55-60. IJCAI/AAAI, 2011.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Sepp Hartung and Frank Kammer and Rolf Niedermeier and Mathias Weller.
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs.
In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC '11), pages 194–206. 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
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
Britta Dorn and Falk Hüffner and Dominikus Krüger and Rolf Niedermeier and Johannes Uhlmann.
Exploiting bounded signal flow for graph orientation based on cause--effect pairs.
In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS '11), pages 104–115. Springer, 2011.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Sepp Hartung and Rolf Niedermeier and Ondrej Suchý.
The Parameterized Complexity of Local Search for TSP, More Refined.
In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC '11), pages 614-623. Springer, 2011.
Bibtex entry Link to publication
Link to original publication
Manuel Sorge and René van Bevern and Rolf Niedermeier and Mathias Weller.
A New View on Rural Postman Based on Eulerian Extension and Matching.
In Proceedings of the 22nd International Workshop on Combinatorial Algorithms (IWOCA'11), pages 310–323. Springer, 2011.
Bibtex entry Link to publication
Link to original publication
Manuel Sorge and René van Bevern and Rolf Niedermeier and Mathias Weller.
From Few Components to an Eulerian Graph by Adding Arcs.
In Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '11), pages 307–318. Springer, 2011.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2011

Nadja Betzler and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier.
Average Parameterization and Partial Kernelization for Computing Medians.
Journal of Computer and System Sciences, 77(4):774–789, Elsevier, 2011.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and René van Bevern and Christian Komusiewicz and Michael R. Fellows and Rolf Niedermeier.
Parameterized Algorithmics for Finding Connected Motifs in Biological Networks.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5):1296-1308, IEEE Computer Society Press, 2011.
Bibtex entry Link to publication
Link to original publication
Britta Dorn and Falk Hüffner and Dominikus Krüger and Rolf Niedermeier and Johannes Uhlmann.
Exploiting bounded signal flow for graph orientation based on cause--effect pairs.
Algorithms for Molecular Biology, 6(1):21, 2011.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier.
A generalization of Nemhauser and Trotter's local optimization theorem.
Journal of Computer and System Sciences, In Press, Corrected Proof(6):1141-1158, Elsevier, 2011.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
Graph-Based Data Clustering with Overlaps.
Discrete Optimization, 8(1):2–17, 2011.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier.
A complexity dichotomy for finding disjoint solutions of vertex deletion problems.
ACM Transactions on Computation Theory, 2(2):5:1–5:23, ACM, 2011.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Ondřej Suchý.
Parameterized Complexity of Arc-Weighted Directed Steiner Problems.
SIAM J. Discrete Math., 25(2):583-599, 2011.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
Deconstructing Intractability --- A Multivariate Complexity Analysis of Interval Constrained Coloring.
Journal of Discrete Algorithms, 9(1):137–151, 2011. 20th Anniversary Edition of the Annual Symposium on Combinatorial Pattern Matching (CPM 2009)
Bibtex entry Link to publication
Link to original publication
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 2010

Nadja Betzler and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier.
Average Parameterization and Partial Kernelization for Computing Medians.
In Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN '10), pages 60–71. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Robert Bredereck and Rolf Niedermeier.
Partial Kernelization for Rank Aggregation: Theory and Experiments.
In Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC '10), pages 26–37. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Hannes Moser and Rolf Niedermeier.
Kernelization Through Tidying---A Case Study Based on s-Plex Cluster Vertex Deletion.
In Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN '10), pages 528–539. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Measuring Indifference: Unit Interval Vertex Deletion.
In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG '10), pages 232–243. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
Frederic Dorn and Hannes Moser and Rolf Niedermeier and Mathias Weller.
Efficient Algorithms for Eulerian Extension.
In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG '10), pages 100–111. 2010.
Bibtex entry Link to publication
Link to original publication
Rudolf Fleischer and Jiong Guo and Rolf Niedermeier and Johannes Uhlmann and Yihui Wang and Mathias Weller and Xi Wu.
Extended Islands of Tractability for Parsimony Haplotyping.
In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM '10), pages 214–226. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Sepp Hartung and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
Exact Algorithms and Experiments for Hierarchical Tree Clustering.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI '10), AAAI Press, 2010.
Bibtex entry Link to publication
Link to original publication
Sepp Hartung and Rolf Niedermeier.
Incremental List Coloring of Graphs, Parameterized by Conservation.
In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC '10), pages 258–270. Springer, 2010.
Bibtex entry Link to publication
Link to original publication
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
Rolf Niedermeier.
Reflections on Multivariate Algorithmics and Problem Parameterization.
In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS '10), pages 17–32. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2010

Nadja Betzler and Jiong Guo and Rolf Niedermeier.
Parameterized computational complexity of Dodgson and Young elections.
Information and Computation, 208(2):165–177, 2010.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Rolf Niedermeier.
Approximation and Fixed-Parameter Algorithms for Consecutive Ones Submatrix Problems.
Journal of Computer and System Sciences, 76(3–4):204–221, 2010.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier and Anke Truss.
Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.
Journal of Discrete Algorithms, 8(1):76–86, 2010.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing.
SIAM Journal on Discrete Mathematics, 24(4):1662–1683, 2010.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Fixed-parameter tractability results for full-degree spanning tree and its dual.
Networks, 56(2):116–130, 2010.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Fixed-Parameter Algorithms for Cluster Vertex Deletion.
Theory of Computing Systems, 47(1):196–217, 2010.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Nadja Betzler and Rolf Niedermeier.
Separator-Based Data Reduction for Signed Graph Balancing.
Journal of Combinatorial Optimization, 20(4):335–360, 2010.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2009

Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond.
How similarity helps to efficiently compute Kemeny rankings.
In Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS '09), pages 657–664. IFAAMAS, 2009.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Susanne Hemmann and Rolf Niedermeier.
A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes.
In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI '09), pages 53–58. 2009.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
Graph-Based Data Clustering with Overlaps.
In Proceedings of the 15th International Computing and Combinatorics Conference (COCOON '09), pages 516–526. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier.
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems.
In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS '09), pages 319–330. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier.
A Generalization of {Nemhauser and Trotter}'s Local Optimization Theorem.
In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS '09), pages 409–420. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2009.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
A more relaxed model for graph-based data clustering: s-plex editing.
In Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM '09), pages 226–239. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Ondrej Suchý.
Parameterized Complexity of Arc-Weighted Directed Steiner Problems.
In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC '09), pages 544–553. Springer, 2009.
Bibtex entry
Link to original publication
Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
Deconstructing Intractability --- A Case Study for Interval Constrained Coloring.
In Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM '09), pages 207–220. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Hannes Moser and Rolf Niedermeier and Manuel Sorge.
Algorithms and Experiments for Clique Relaxations---Finding Maximum $s$-Plexes.
In Proceedings of the 8th International Symposium on Experimental Algorithms (SEA '09), pages 233–244. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Mathias Weller and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann.
On Making Directed Graphs Transitive.
In Proceedings of the 11th International Symposium on Algorithms and Data Structures (WADS '09), pages 542–553. Springer, 2009.
Bibtex entry Link to publication
Link to original publication

Book Chapters 2009

Jiong Guo and Hannes Moser and Rolf Niedermeier.
Iterative Compression for Exactly Solving {NP}-Hard Minimization Problems.
In Algorithmics of Large and Complex Networks, pages 65–80. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Rolf Niedermeier and Sebastian Wernicke.
Fixed-parameter algorithms for graph-modeled data clustering.
In Clustering Challenges in Biological Networks, pages 3–28. World Scientific, 2009.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2009

Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond.
Fixed-parameter algorithms for Kemeny rankings.
Theoretical Computer Science, 410(45):4554–4570, 2009.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Isolation Concepts for Clique Enumeration: Comparison and Computational Experiments.
Theoretical Computer Science, 410(52):5384–5397, 2009.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and Falk Hüffner and Hannes Moser and Rolf Niedermeier.
Isolation Concepts for Efficiently Enumerating Dense Subgraphs.
Theoretical Computer Science, 410(38–40):3640–3654, 2009.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2008

Nadja Betzler and Jiong Guo and Rolf Niedermeier.
Parameterized Computational Complexity of Dodgson and Young Elections.
In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT '08), pages 402–413. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Michael R. Fellows and Christian Komusiewicz and Rolf Niedermeier.
Parameterized Algorithms and Hardness Results for Some Graph Motif Problems.
In Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM '08), pages 31–43. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond.
Fixed-Parameter Algorithms for Kemeny Scores.
In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM '08), pages 60–71. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Fixed-Parameter Algorithms for Cluster Vertex Deletion.
In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN '08), pages 711–722. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier.
Enumerating isolated cliques in synthetic and financial networks.
In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA '08), pages 405–416. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Oriana Ponta and Falk Hüffner and Rolf Niedermeier.
Speeding up Dynamic Programming for Some {NP}-hard Graph Recoloring Problems.
In Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation (TAMC '08), pages 490–501. Springer, 2008.
Bibtex entry Link to publication
Link to original publication

Book chapters 2008

Michael Dom and Falk Hüffner and Rolf Niedermeier.
Tiefensuche (Ariadne und Co.).
In Taschenbuch der Algorithmen, pages 61–73. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Rolf Niedermeier and Sebastian Wernicke.
Developing Fixed-Parameter Algorithms to Solve Combinatorially Explosive Biological Problems.
In Bioinformatics, pages 395–421. Humana Press, 2008.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2008

Michael Dom and Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Red-blue covering problems and the consecutive ones property.
Journal of Discrete Algorithms, 6(3):393–407, 2008.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Closest 4-leaf power is fixed-parameter tractable.
Discrete Applied Mathematics, 156(18):3345–3361, 2008.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Data reduction and exact algorithms for clique cover.
ACM Journal of Experimental Algorithmics, 13:2.2:1–2.2:15, 2008.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Johannes Uhlmann.
Two fixed-parameter algorithms for Vertex Covering by Paths on Trees.
Information Processing Letters, 106(2):81–86, 2008.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Daniel Raible.
Improved Algorithms and Complexity Results for Power Domination in Graphs.
Algorithmica, 52(2):177–202, 2008.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Falk Hüffner and Erhan Kenar and Rolf Niedermeier and Johannes Uhlmann.
Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs.
European Journal of Operational Research, 186(2):542–553, 2008.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Rolf Niedermeier and Sebastian Wernicke.
Techniques for Practical Fixed-Parameter Algorithms.
The Computer Journal, 51(1):7–25, 2008.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2007

Michael Dom and Rolf Niedermeier.
The search for consecutive ones submatrices: faster and more general.
In Proceedings of the 3rd Workshop on Algorithms and Complexity in Durham (ACiD '07), College Publications, 2007.
Bibtex entry Link to publication
Michael Dom and Jiong Guo and Rolf Niedermeier.
Approximability and parameterized complexity of consecutive ones submatrix problems.
In Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC '07), pages 680–691. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
Probe matrix problems: totally balanced matrices.
In Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM '07), pages 368–377. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
Linear problem kernels for NP-hard problems on planar graphs.
In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP '07), pages 375–386. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Nadja Betzler and Rolf Niedermeier.
Optimal edge deletions for signed graph balancing.
In Proceedings of the 6th Workshop on Experimental Algorithms (WEA '07), pages 297–310. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Christian Komusiewicz and Hannes Moster and Rolf Niedermeier.
Isolation concepts for enumerating dense subgraphs.
In Proceedings of the 13th International Computing and Combinatorics Conference (COCOON '07), pages 140–150. Springer, 2007.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2007

Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier and Hans-Peter Piepho and Ramona Schmid.
Algorithms for Compact Letter Displays: Comparison and Evaluation.
Computational Statistics & Data Analysis, 52(2):725–736, 2007.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Parameterized Complexity of Vertex Cover Variants.
Theory of Computing Systems, 41(3):501–520, 2007.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
Invitation to data reduction and problem kernelization.
SIGACT News, 38(1):31–45, 2007.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Jörg Vogel and Michael Fothe and Mirko König.
Das Knotenüberdeckungsproblem - Eine Fallstudie zur Didaktik NP-schwerer Probleme (Teil 1 und 2).
LOG IN, 27(146/147 (Teil 1), 148 (Teil 2)):53–59 (Teil 1), 81–89 (Teil 2), 2007.
Bibtex entry Link to publication

Conference Publications 2006

Jochen Alber and M. Brosemann and Falk Hüffner and Rolf Niedermeier.
Matrix robustness, with an application to power system observability.
In Proceedings of the 2nd Algorithms and Complexity in Durham (ACiD '06), pages 37–48. College Publications, 2006.
Bibtex entry Link to publication
Jochen Alber and Britta Dorn and Rolf Niedermeier.
A general data reduction scheme for domination in graphs.
In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '06), pages 137–147. Springer, 2006.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Minimum membership set covering and the consecutive ones property.
In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT '06), pages 339–350. Springer, 2006.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier and Anke Truß.
Fixed-parameter tractability results for feedback set problems in tournaments.
In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC '06), pages 320–331. Springer, 2006.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Data reduction, exact, and heuristic algorithms for clique cover.
In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX '06), pages 86–94. 2006.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Fixed-parameter tractability results for full-degree spanning tree and its dual.
In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC '06), pages 203–214. 2006.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Falk Hüffner and Erhan Kenar and Rolf Niedermeier and Johannes Uhlmann.
Complexity and exact algorithms for multicut.
In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '06), pages 303–312. Springer, 2006.
Bibtex entry Link to publication
Link to original publication

Books 2006

Rolf Niedermeier.
Invitation to Fixed-Parameter Algorithms.
Oxford University Press, 2006.
Bibtex entry
Link to original publication

Journal Publications 2006

Jochen Alber and Nadja Betzler and Rolf Niedermeier.
Experiments on data reduction for optimal domination in networks.
Annals of Operations Research, 146(1):105–117, 2006.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Rolf Niedermeier and Johannes Uhlmann.
Tree decompositions of graphs: saving memory in dynamic programming.
Discrete Optimization, 3(3):220–229, 2006.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Error Compensation in Leaf Power Problems.
Algorithmica, 44(4):363–381, 2006.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jens Gramm and Rolf Niedermeier.
On the parameterized intractability of motif search problems.
Combinatorica, 26(2):141–167, 2006.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Rolf Niedermeier.
Pattern matching for arc-annotated sequences.
ACM Transactions on Algorithms, 2(1):44–65, 2006.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier and Sebastian Wernicke.
Compression-based fixed-parameter algorithms for Feedback Vertex Set and Edge Bipartization.
Journal of Computer and System Sciences, 72(8):1368–1396, 2006.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
The computational complexity of avoiding forbidden submatrices by row deletions.
International Journal of Foundations of Computer Science, 17(6):1467–1484, 2006.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Rolf Niedermeier.
Parameterized Intractability of Distinguishing Substring Selection.
Theory of Computing Systems, 39(4):545–560, 2006.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
Exact algorithms and applications for tree-like weighted set cover.
Journal of Discrete Algorithms, 4(4):608–622, 2006.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
A fixed-parameter tractability result for multicommodity demand flow in trees.
Information Processing Letters, 97(3):109–114, 2006.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2005

Michael Dom and Jiong Guo and Rolf Niedermeier.
Bounded degree closest k-tree power is NP-complete.
In Proceedings of the 11th International Computing and Combinatorics Conference (COCOON '05), pages 757–766. Springer, 2005.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Extending the Tractability Border for Closest Leaf Powers.
In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG '05), pages 397–408. Springer, 2005.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Parameterized complexity of generalized vertex cover problems.
In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS '05), pages 36–48. Springer, 2005.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier and Daniel Raible.
Improved algorithms and complexity results for power domination in graphs.
In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT '05), pages 172–184. Springer, 2005.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Jens Gramm and Falk Hüffner and Rolf Niedermeier and Sebastian Wernicke.
Improved fixed-parameter algorithms for two feedback set problems.
In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS '05), pages 158–168. Springer, 2005.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2005

Jochen Alber and Hongbing Fan and Michael R. Fellows and Henning Fernau and Rolf Niedermeier and Frances A. Rosamond and Ulrike Stege.
A refined search tree technique for Dominating Set on planar graphs.
Journal of Computer and System Sciences, 71(4):385–405, 2005.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Frederic Dorn and Rolf Niedermeier.
Experimental evaluation of a tree decomposition based algorithm for vertex cover on planar graphs.
Discrete Applied Mathematics, 145(2):219–231, 2005.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation.
Theory of Computing Systems, 38(4):373–392, 2005.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Rolf Niedermeier.
Fixed-parameter tractability and data reduction for multicut in trees.
Networks, 46(3):124–135, 2005.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2004

Jochen Alber and Jens Gramm and Jiong Guo and Rolf Niedermeier and Sebastian Wernicke.
Avoiding forbidden submatrices by row deletions.
In Proceedings of the 30th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM '04), pages 349–360. Springer, 2004.
Bibtex entry Link to publication
Link to original publication
Nadja Betzler and Rolf Niedermeier and J. Uhlmann.
Tree decompositions of graphs: Saving memory in dynamic programming.
In Proceedings of the Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW '04), 2004.
Bibtex entry Link to publication
Link to original publication
Hans L. Bodlaender and C. M. H. de Figueiredo and M. Gutierrez and Ton Kloks and Rolf Niedermeier.
Simple Max-Cut for split-indifference graphs and graphs with few P4's.
In Proceedings of the 3rd Workshop on Efficient and Experimental Algorithms (WEA '04), pages 87–99. Springer, 2004.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Error compensation in leaf root problems.
In Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC '04), pages 389–401. Springer, 2004.
Bibtex entry
Link to original publication
Jiong Guo and Falk Hüffner and Rolf Niedermeier.
A Structural View on Parameterizing Problems: Distance from Triviality.
In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC '04), pages 162–173. Springer, 2004.
Bibtex entry
Link to original publication
Rolf Niedermeier.
Ubiquitous parameterization - Invitation to fixed-parameter algorithms.
In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pages 84–103. Springer, 2004.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2004

Jochen Alber and Jens Gramm and Jiong Guo and Rolf Niedermeier.
Computing the similarity of two sequences with nested arc annotations.
Theoretical Computer Science, 312(2–3):337–358, 2004.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Henning Fernau and Rolf Niedermeier.
Parameterized complexity: exponential speed-up for planar graph problems.
Journal of Algorithms, 52:26–56, 2004.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Michael R. Fellows and Rolf Niedermeier.
Polynomial time data reduction for Dominating Set.
Journal of the ACM, 51(3):363–384, 2004.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems.
Algorithmica, 39(4):321–347, 2004.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2003

Jochen Alber and Nadja Betzler and Rolf Niedermeier.
Experiments on data reduction for optimal domination in networks.
In Proceedings of the International Network Optimization Conference (INOC '03), pages 1–6. 2003.
Bibtex entry Link to publication
Jens Gramm and Jiong Guo and Rolf Niedermeier.
On exact and approximation algorithms for Distinguishing Substring Selection.
In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT '03), pages 195–209. 2003.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Graph-modeled data clustering: fixed-parameter algorithms for clique generation..
In Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC '03), pages 108–119. Springer, 2003.
Bibtex entry
Link to original publication
Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier.
Automated generation of search tree algorithms for graph modification problems.
In Proceedings of the 11th Annual European Symposium on Algorithms (ESA '03), pages 642–653. Springer, 2003.
Bibtex entry
Link to original publication

Journal Publications 2003

Jochen Alber and Henning Fernau and Rolf Niedermeier.
Graph separators: a parameterized view.
Journal of Computer and System Sciences, 67(4):808–832, 2003.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Edward A. Hirsch and Rolf Niedermeier and Peter Rossmanith.
Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT.
Discrete Applied Mathematics, 130(2):139–155, 2003.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier.
A fixed-parameter algorithm for Minumium Quartet Inconsistency.
Journal of Computer and System Sciences, 67(4):723–741, 2003.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier and Peter Rossmanith.
Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems.
Algorithmica, 37(1):25-42, 2003.
Bibtex entry
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
An efficient fixed parameter algorithm for 3-Hitting Set.
Journal of Discrete Algorithms, 1:89–102, 2003.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
On efficient fixed-parameter algorithms for Weighted Vertex Cover.
Journal of Algorithms, 47:63–77, 2003.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2002

Jochen Alber and Michael R. Fellows and Rolf Niedermeier.
Efficient data reduction for Dominating Set: a linear problem kernel for the planar case.
In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT '02), pages 150–159. Springer, 2002.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Rolf Niedermeier.
Improved tree decomposition based algorithms for domination-like problems.
In Proceedings of the 5th Latin American Theoretical INformatics (LATIN '02), pages 613–627. Springer, 2002.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Jens Gramm and Jiong Guo and Rolf Niedermeier.
Towards optimally solving the Longest Common Subsequence problem for sequences with nested arc annotations in linear time.
In Proceedings of the 13th Annual Symposium on Combinatorial Pattern matching (CPM '02), pages 99–114. 2002.
Bibtex entry Link to publication
Link to original publication
Michael R. Fellows and Jens Gramm and Rolf Niedermeier.
On the Parameterized Intractability of Closest Substring and Related Problems.
In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS '02), pages 262–273. Springer, 2002.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier.
Breakpoint medians and breakpoint phylogenies: A fixed-parameter approach.
In Proceedings of the European Conference on Computational Biology 2002 (ECCB '02), pages 128–139. Oxford University Press, 2002.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Jiong Guo and Rolf Niedermeier.
Pattern matching for arc-annotated sequences.
In Proceedings of the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '02), pages 182–193. 2002.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2002

Jochen Alber and Hans L. Bodlaender and Henning Fernau and Ton Kloks and Rolf Niedermeier.
Fixed parameter algorithms for Dominating Set and related problems on planar graphs.
Algorithmica, 33:461–493, 2002.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Klaus Reinhardt and Peter Sanders.
Towards optimal locality in mesh-indexings.
Discrete Applied Mathematics, 117(1–3):211–237, 2002.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2001

Jochen Alber and Hongbing Fan and Michael R. Fellows and Henning Fernau and Rolf Niedermeier and Frances Rosamond and Ulrike Stege.
Refined search tree technique for Dominating Set on planar graphs.
In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS '01), pages 111–122. Springer, 2001.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Henning Fernau and Rolf Niedermeier.
Parameterized complexity: Exponential speed-up for planar graph problems.
In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP '01), pages 261–272. Springer, 2001.
Bibtex entry Link to publication
Link to original publication
Jochen Alber and Henning Fernau and Rolf Niedermeier.
Graph separators: A parameterized view.
In Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON '01), pages 318–327. Springer, 2001.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier and Peter Rossmanith.
Exact solutions for Closest String and related problems.
In Proceedings of the 12th Annual International Symposium on Algorithms and Computation (ISAAC '01), pages 441–452. Springer, 2001.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier.
Minimum quartet inconsistency is fixed parameter tractable.
In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM '01), pages 241–256. Springer, 2001.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2001

Jochen Alber and Jens Gramm and Rolf Niedermeier.
Faster exact algorithms for hard problems: A parameterized point of view.
Discrete Mathematics, 229(1–3):3–27, 2001.
Bibtex entry Link to publication
Link to original publication
Henning Fernau and Rolf Niedermeier.
An efficient exact algorithm for constraint bipartite vertex cover.
Journal of Algorithms, 38(2):374–410, 2001.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Stefan Edelkamp and Henning Fernau and Rolf Niedermeier.
Finding Optimal Solutions to {Atomix}.
, 2174:229–243, Springer, 2001.
Bibtex entry
Link to original publication

Conference Publications 2000

Jochen Alber and Hans L. Bodlaender and Henning Fernau and Rolf Niedermeier.
Fixed parameter algorithms for Planar Dominating Set and related problems.
In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT '00), pages 97–110. 2000.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Rolf Niedermeier.
Faster exact solutions for Max2Sat.
In Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC '00), pages 174–186. Springer, 2000.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
On efficient fixed parameter algorithms for Weighted Vertex Cover.
In Proceedings of the 11th Annual International Symposium on Algorithms And Computation (ISAAC '00), pages 180–191. Springer, 2000.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2000

Jochen Alber and Rolf Niedermeier.
On multidimensional curves with Hilbert property.
Theory of Computing Systems, 33:295–312, 2000.
Bibtex entry Link to publication
Link to original publication
Klaus-Jörn Lange and Rolf Niedermeier.
Data-independences of read, write, and control structures in PRAM computations.
Journal of Computer and System Sciences, 60:109–144, 2000.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
A general method to speed up fixed-parameter-tractable algorithms.
Information Processing Letters, 73:125–129, 2000.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
New upper bounds for Maximum Satisfiability.
Journal of Algorithms, 36:63–88, 2000.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1999

Henning Fernau and Rolf Niedermeier.
An efficient exact algorithm for Constraint Bipartite Vertex Cover.
In Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science (MFCS '99), pages 387–397. Springer, 1999.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
New upper bounds for MaxSat.
In Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP '99), pages 575–584. Springer, 1999.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
Upper bounds for Vertex Cover further improved.
In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS '99), pages 561–570. Springer, 1999.
Bibtex entry Link to publication
Link to original publication

Journal Publications 1999

Manfred Kunde and Rolf Niedermeier and Klaus Reinhardt and Peter Rossmanith.
Optimal deterministic sorting and routing on grids and tori with diagonals.
Algorithmica, 25(4):438–42, 1999.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1998

Jochen Alber and Rolf Niedermeier.
On multi-dimensional Hilbert indexings.
In Proceedings of the 4th International Computing and Combinatorics Conference (COCOON '98), pages 329–338. Springer, 1998.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier.
Some prospects for efficient fixed parameter algorithms.
In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM '98), pages 168–185. Springer, 1998.
Bibtex entry Link to publication
Link to original publication

Journal Publications 1998

Rolf Niedermeier and Peter Rossmanith.
Unambiguous computations and locally definable acceptance types.
Theoretical Computer Science, 194:137–161, 1998.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1997

Rolf Niedermeier and Klaus Reinhardt and Peter Sanders.
Towards optimal locality in mesh-indexings.
In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT '97), pages 364–375. Springer, 1997.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1996

Rolf Niedermeier.
Recursively divisible problems.
In Proceedings of the 7th International Symposium on Algorithms and Computation (ISAAC '96), pages 83–192. Springer, 1996.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1995

Manfred Kunde and Rolf Niedermeier and Klaus Reinhardt and Peter Rossmanith.
Optimal average case sorting on arrays.
In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science (STACS '95), pages 503–514. Springer, 1995.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
PRAM's towards realistc parallelism: BRAM's.
In Proceedings of the 10th International Conference on Fundamentals of Computation Theory (FCT' 95), pages 363–373. Springer, 1995.
Bibtex entry Link to publication
Link to original publication

Journal Publications 1995

Rolf Niedermeier and Peter Rossmanith.
Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits.
Information and Computation, 118(2):227–245, 1995.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
On optimal {OROW-PRAM} algorithms for computing recursively defined functions.
Parallel Processing Letters, 5(2):299–309, 1995.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1994

Manfred Kunde and Rolf Niedermeier and Peter Rossmanith.
Faster sorting and routing on grids with diagonals.
In Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS '94), pages 225–236. Springer, 1994.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1993

Klaus-Jörn Lange and Rolf Niedermeier.
Data-independences of parallel random access machines.
In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '93), pages 104–113. Springer, 1993.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
Extended locally definable acceptance types.
In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science (STACS '93), pages 473–483. Springer, 1993.
Bibtex entry Link to publication
Link to original publication
Rolf Niedermeier and Peter Rossmanith.
On the power of reading and writing simultaneously in parallel computations.
In Proceedings of the 4th International Symposium on Algorithms and Computation (ISAAC '93), pages 240–249. Springer, 1993.
Bibtex entry Link to publication
Link to original publication

Conference Publications 1992

Rolf Niedermeier and Peter Rossmanith.
Unambiguous simulations of auxiliary pushdown automata and circuits.
In Proceedings of the 1st Symposium on Latin American Theoretical Informatics, pages 387–400. Springer, 1992.
Bibtex entry Link to publication
Link to original publication