direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Conference Publications 2019

Till Fluschnik and Piotr Skowron and Mervin Triphaus and Kai Wilker.
Fair Knapsack.
In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI '19), AAAI Press, 2019. Accepted for publication.
Bibtex entry Link to publication
George B. Mertzios and Hendrik Molter and Viktor Zamaraev.
Sliding Window Temporal Graph Coloring.
In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI '19), AAAI Press, 2019. Accepted for publication.
Bibtex entry Link to publication

Conference Publications 2018

Haris Aziz and Edith Elkind and Shenwei Huang and Martin Lackner and Luis Sánchez-Fernández and Piotr Skowron.
On the Complexity of Extended and Proportional Justified Representation.
In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI '18), 2018. Accepted for publication.
Bibtex entry Link to publication
Matthias Bentert and Alexander Dittmann and Leon Kellerhals and André Nichterlein and Rolf Niedermeier.
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality.
In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), pages 125:1–125:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
Bibtex entry Link to publication
Matthias Bentert and Josef Malík and Mathias Weller.
Tree Containment With Soft Polytomies.
In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '18), pages 9:1–9:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
Bibtex entry Link to publication
Matthias Bentert and Anne-Sophie Himmel and Hendrik Molter and Marco Morik and Rolf Niedermeier and René Saitenmacher.
Listing All Maximal k-Plexes in Temporal Graphs.
In Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM '18), pages 41–46. IEEE Computer Society, 2018.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Till Fluschnik and Oxana Yu. Tsidulko.
Parameterized algorithms and data reduction for safe convoy routing.
In Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS '18), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Accepted for publication.
Bibtex entry Link to publication
Robert Bredereck and Andrzej Kaczmarczyk and Rolf Niedermeier.
Envy-Free Allocations Respecting Social Networks.
In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '18), pages 283–291. IFAAMAS, 2018.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Piotr Faliszewski and Ayumi Igarashi and Martin Lackner and Piotr Skowron.
Multiwinner Elections with Diversity Constraints.
In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI '18), pages 933–940. 2018.
Bibtex entry Link to publication
Link to original publication
Markus Brill and Till Fluschnik and Vincent Froese and Brijnesh Jain and Rolf Niedermeier and David Schultz.
Exact Mean Computation in Dynamic Time Warping Spaces.
In Proceedings of the SIAM International Conference on Data Mining (SDM '18), pages 540–548. SIAM, 2018.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Hendrik Molter and Manuel Sorge and Ondrej Suchý.
Cluster Editing in Multi-Layer and Temporal Graphs.
In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Accepted for publication.
Bibtex entry Link to publication
Pavel Dvořák and Dušan Knop and Tomáš Toufar.
Target Set Selection in Dense Graph Classes.
In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), pages 18:1–18:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Accepted for publication.
Bibtex entry Link to publication
Henning Fernau and Till Fluschnik and Danny Hermelin and Andreas Krebs and Hendrik Molter and Rolf Niedermeier.
Diminishable Parameterized Problems and Strict Polynomial Kernelization.
In Proceedings of the 14th Conference on Computability in Europe (CiE '18), pages 161–171. Springer International Publishing, 2018.
Bibtex entry Link to publication
Link to original publication
Till Fluschnik and Hendrik Molter and Rolf Niedermeier and Philipp Zschoche.
Temporal Graph Classes: A View Through Temporal Separators.
In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '18), pages 216–227. Springer International Publishing, 2018.
Bibtex entry Link to publication
Link to original publication
Till Fluschnik and George B. Mertzios and André Nichterlein.
Kernelization Lower Bounds for Finding Constant-Size Subgraphs.
In Proceedings of the 14th Conference on Computability in Europe (CiE '18), pages 183–193. Springer International Publishing, 2018.
Bibtex entry Link to publication
Link to original publication
Clemens Hoffmann and Hendrik Molter and Manuel Sorge.
The Parameterized Complexity of Centrality Improvement in Networks.
In Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '18), pages 111–124. Springer International Publishing, 2018.
Bibtex entry Link to publication
Link to original publication
Viatcheslav Korenwein and André Nichterlein and Rolf Niedermeier and Philipp 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), pages 53:1–53:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Accepted for publication.
Bibtex entry Link to publication
Junjie Luo and Hendrik Molter and André Nichterlein and Rolf 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. Accepted for publication.
Bibtex entry Link to publication
Junjie Luo and Hendrik Molter and Ondrej Suchý.
A Parameterized Complexity View on Collapsing k-Cores.
In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC '18), 2018. Accepted for publication.
Bibtex entry Link to publication
Marcelo Garlet Millani and Hendrik Molter and Rolf Niedermeier and Manuel Sorge.
Efficient Algorithms for Measuring the Funnel-likeness of DAGs.
In Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO '18), pages 183–195. Springer International Publishing, 2018.
Bibtex entry Link to publication
Link to original publication
Philipp Zschoche and Till Fluschnik and Hendrik Molter and Rolf Niedermeier.
The Complexity of Finding Small Separators in Temporal Graphs.
In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS '18), pages 45:1–45:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2018

René van Bevern and Vincent Froese and Christian Komusiewicz.
Parameterizing edge modification problems above lower bounds.
Theory of Computing Systems, 62(3):739–770, 2018.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Till Fluschnik and George B. Mertzios and Hendrik Molter and Manuel Sorge and Ondrej Suchý.
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs.
Discrete Optimization, 30:20–50, 2018.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Falk Hüffner and Stefan Kratsch.
Parameterized complexity of team formation in social networks.
Theoretical Computer Science, 717:26–36, 2018.
Bibtex entry
Link to original publication
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.
Algorithmica, 2018. Available online.
Bibtex entry Link to publication
Link to original publication
Markus Brill and Till Fluschnik and Vincent Froese and Brijnesh Jain and Rolf Niedermeier and David Schultz.
Exact Mean Computation in Dynamic Time Warping Spaces.
Data Mining and Knowledge Discovery, 2018. Online first.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Ugo Paavo Finnendahl.
On the Number of Single-Peaked Narcissistic or Single-Crossing Narcissistic Preferences.
Discrete Mathematics, 2018. To appear
Bibtex entry Link to publication
Cristina Bazgan, Till Fluschnik, André Nichterlein, Rolf Niedermeier, and Maximilian Stahlberg.
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.
Networks, 2018. Accepted for publication.
Bibtex entry Link to publication
Till Fluschnik and Danny Hermelin and André Nichterlein and Rolf Niedermeier.
Fractals for Kernelization Lower Bounds.
SIAM Journal on Discrete Mathematics, 32(1):656–681, 2018.
Bibtex entry Link to publication
Link to original publication
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?.
Algorithmica, 2018.
Bibtex entry Link to publication
Anne-Sophie Himmel and Clemens Hoffmann and Pascal Kunz and Vincent Froese and Manuel Sorge.
Computational Complexity Aspects of Point Visibility Graphs.
Discrete Applied Mathematics, 2018. Available online.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and André Nichterlein and Rolf Niedermeier and Marten Picker.
Exact Algorithms for Finding Well-Connected 2-Clubs in Sparse Real-World Graphs: Theory and Experiments.
European Journal of Operational Research, 2018. Accepted for publication.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2017

Haris Aziz and Edith Elkind and Piotr Faliszewski and Martin Lackner and Piotr Skowron.
The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality.
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 84–90. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original 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), pages 96–110. Springer International Publishing, 2017.
Bibtex entry Link to publication
Link to original publication
Matthias Bentert and René van Bevern and André Nichterlein and Rolf 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), pages 26–40. Springer International Publishing, 2017.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Till Fluschnik and George B. Mertzios and Hendrik Molter and Manuel Sorge and Ondrej Suchý.
Finding Secluded Places of Special Interest in Graphs.
In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC '16), pages 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Christian Komusiewicz and Stefan Kratsch and Hendrik Molter and Rolf Niedermeier and Manuel Sorge.
Assessing the Computational Complexity of Multi-Layer Subgraph Detection.
In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC '17), pages 128–139. Springer International Publishing, 2017.
Bibtex entry Link to publication
Link to original publication
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 Link to publication
Link to original publication
Robert Bredereck and Edith Elkind.
Manipulating Opinion Diffusion in Social Networks.
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 894–900. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Andrzej Kaczmarczyk and Rolf Niedermeier.
On Coalitional Manipulation for Multiwinner Elections: Shortlisting.
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 887–893. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Ugo Paavo Finnendahl and Rolf Niedermeier.
Stable Roommate with Narcissistic, Single-Peaked, and Single-Crossing Preferences.
In Proceedings of the 5th International Conference on Algorithmic Decision Theory (ADT '17), pages 315–330. Springer, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Rolf Niedermeier and Svetlana Obraztsova and Nimrod Talmon.
Teams in Online Scheduling Polls: Game-Theoretic Aspects.
In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI '17), pages 390–396. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Piotr Faliszewski and Andrzej Kaczmarczyk and Rolf Niedermeier and Piotr Skowron and Nimrod Talmon.
Robustness Among Multiwinner Voting Rules.
In Proceedings of the Algorithmic Game Theory: 10th International Symposium (SAGT '17), pages 80–92. Springer, 2017.
Bibtex entry Link to publication
Link to original publication
Markus Brill and Jean-François Laslier and Piotr Skowron.
Multiwinner Approval Rules as Apportionment Methods.
In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI '17), pages 414–420. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Markus Brill and Rupert Freeman and Svante Janson and Martin Lackner.
Phragm\´en's Voting Methods and Justified Representation.
In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI '17), pages 406–413. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Piotr Faliszewski and Piotr Skowron and Nimrod Talmon.
Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules.
In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '17), pages 6–14. ACM, 2017.
Bibtex entry Link to publication
Link to original publication
Piotr Faliszewski and Piotr Skowron and Arkadii Slinko and Nimrod Talmon.
Multiwinner Rules on Paths From k-Borda to Chamberlin-Courant.
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 192-198. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication
Till Fluschnik and Meike Hatzel and Steffen Härtlein and Hendrik Molter and Henning Seidler.
The Minimum Shared Edges Problem on Grid-like Graphs.
In Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '17), pages 249–262. Springer International Publishing, 2017.
Bibtex entry Link to publication
Link to original publication
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
Link to original publication
Till Fluschnik and Marco Morik and Manuel Sorge.
The Complexity of Routing with Few Collisions.
In Proceedings of the 21st Symposium on Fundamentals of Computation Theory (FCT '17), pages 257–270. Springer International Publishing, 2017.
Bibtex entry Link to publication
Link to original publication
Ayumi Igarashi and Robert Bredereck and Edith Elkind.
On Parameterized Complexity of Group Activity Selection Problems on Social Networks.
In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '17), pages 1575–1577. ACM, 2017.
Bibtex entry Link to publication
Link to original publication
Leon Kellerhals and Viatcheslav Korenwein and Philipp Zschoche and Robert Bredereck and Jiehua Chen.
On the Computational Complexity of Variants of Combinatorial Voter Control in Elections.
In Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation (TAMC '17), pages 348–361. 2017.
Bibtex entry Link to publication
Link to original publication
George B. Mertzios and André Nichterlein and Rolf 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), pages 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
Bibtex entry Link to publication
Link to original publication
Piotr Skowron and Martin Lackner and Markus Brill and Dominik Peters and Edith Elkind.
Proportional Rankings.
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 409–415. AAAI Press, 2017.
Bibtex entry Link to publication
Link to original publication

Journal Publications 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, 220:134–160, 2017.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Robert Bredereck and Laurent Bulteau and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Gerhard J. Woeginger.
Partitioning Perfect Graphs into Stars.
Journal of Graph Theory, 85(2):297–335, 2017.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Rolf Niedermeier and Ondrej Suchý.
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack.
Journal of Scheduling, 20(3):255–265, 2017.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Rolf Niedermeier and Toby Walsh.
Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty.
Journal of Artificial Intelligence Research, 59:133–173, 2017.
Bibtex entry
Link to original publication
Laurent Bulteau and Stefan Fafianie and Vincent Froese and Rolf Niedermeier and Nimrod Talmon.
The Complexity of Finding Effectors.
Theory of Computing Systems, 60(2):253–279, 2017.
Bibtex entry Link to publication
Link to original publication
Vincent Froese and Iyad Kanj and André Nichterlein and Rolf Niedermeier.
Finding Points in General Position.
International Journal of Computational Geometry & Applications, 27(4):277–296, 2017.
Bibtex entry Link to publication
Link to original publication
Archontia C. Giannopoulou and George B. Mertzios and Rolf Niedermeier.
Polynomial Fixed-parameter Algorithms: {A} Case Study for Longest Path on Interval Graphs.
Theoretical Computer Science, 2017. Accepted for publication.
Bibtex entry Link to publication
Link to original publication
Anne-Sophie Himmel and Hendrik Molter and Rolf Niedermeier and Manuel Sorge.
Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs.
Social Network Analysis and Mining, 7(1):35:1–35:16, 2017.
Bibtex entry Link to publication
Link to original publication
Kratsch, Stefan and Sorge, Manuel.
On Kernelization and Approximation for the Vector Connectivity Problem.
Algorithmica, 79(1):96–138, 2017.
Bibtex entry Link to publication
Link to original publication
Piotr Skowron and Piotr Faliszewski.
Chamberlin-Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time.
Journal of Artificial Intelligence Research, 60:687–716, 2017.
Bibtex entry Link to publication
Link to original publication
Piotr Skowron.
FPT Approximation Schemes for Maximizing Submodular Functions.
Information and Computation, 257:65–78, 2017.
Bibtex entry Link to publication
Link to original publication
Nimrod Talmon and Sepp Hartung.
The complexity of degree anonymization by graph contractions.
Information and Computation, 2017. Accepted for publication.
Bibtex entry
Link to original publication

Conference Publications 2016

René van Bevern and Hendrik Molter and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge and Toby Walsh.
h-Index Manipulation by Undoing Merges.
In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI '16), pages 895–903. IOS Press, 2016.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Iyad A. Kanj and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge.
Twins in Subdivision Drawings of Hypergraphs.
In Proceedings of the 24th International Symposium on Graph Drawing & Network Visualization (GD '16), Springer, 2016.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Robert Bredereck and Laurent Bulteau and Christian Komusiewicz and Nimrod Talmon and Gerhard J. Woeginger.
Precedence-constrained scheduling problems parameterized by partial order width.
In Proceedings of the International Conference on Discrete Optimization and Operations Research (DOOR '16), pages 105–120. Springer, 2016.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Vincent Froese and Christian Komusiewicz.
Parameterizing edge modification problems above lower bounds.
In Proceedings of the 11th International Computer Science Symposium in Russia (CSR '16), pages 57–72. Springer, 2016.
Bibtex entry Link to publication
Link to original publication
Berhard Bliem and Robert Bredereck and Rolf Niedermeier.
Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels.
In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI '16), pages 102–108. AAAI Press, 2016.
Bibtex entry
Link to original publication
Robert Bredereck and Jiehua Chen and Falk Hüffner and Stefan Kratsch.
Parameterized Complexity of Team Formation in Social Networks.
In Proceedings of the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM '16), pages 137–149. 2016.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Piotr Skowron and Nimrod Talmon.
Complexity of Shift Bribery in Committee Elections.
In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI '16), pages 2452–2458. 2016.
Bibtex entry
Link to original 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), pages 25:1–25:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
Bibtex entry Link to publication
Link to original 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), pages 7–14. 2016.
Bibtex entry Link to publication
Link to original publication
Anne-Sophie Himmel and Hendrik Molter and Rolf Niedermeier and Manuel Sorge.
Enumerating maximal cliques in temporal graphs.
In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (ASONAM '16), pages 337–344. IEEE Computer Society, 2016.
Bibtex entry Link to publication
Link to original publication
Iyad A. Kanj and Christian Komusiewicz and Manuel Sorge and Erik Jan van Leeuwen.
Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs.
In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '16), pages 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
Bibtex entry Link to publication
Link to original publication

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
René van Bevern and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge and Toby Walsh.
H-Index Manipulation by Merging Articles: Models, Theory, and Experiment.
Artificial Intelligence, 260:19–35, 2016.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Rolf Niedermeier and Ondřej Suchý.
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack.
Journal of Scheduling, Springer, 2016. In press
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Gerhard J. Woeginger.
Are there any nicely structured preference profiles nearby?.
Mathematical Social Sciences, 79:61–73, 2016.
Bibtex entry
Link to original publication
Robert Bredereck and Nimrod Talmon.
NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting.
Information Processing Letters, 116(2):147–152, 2016.
Bibtex entry
Link to original publication
Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon.
Large-Scale Election Campaigns: Combinatorial Shift Bribery.
Journal of Artificial Intelligence Research, 55:603–652, 2016.
Bibtex entry
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.
Information and Computation, 251:140–164, 2016.
Bibtex entry
Link to original publication
Laurent Bulteau and Vincent Froese and Sepp Hartung and Rolf Niedermeier.
Co-Clustering Under the Maximum Norm.
Algorithms, 9(1):17, 2016.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Vincent Froese and Nimrod Talmon.
Multi-Player Diffusion Games on Graph Classes.
Internet Mathematics, 12(6):363–380, 2016.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Vincent Froese and Konstantin Kutzkov and Rasmus Pagh.
Triangle counting in dynamic graph streams.
Algorithmica, 76(1):259–278, 2016.
Bibtex entry Link to publication
Link to original publication
Vincent Froese and René van Bevern and Rolf Niedermeier and Manuel Sorge.
Exploiting Hidden Structure in Selecting Dimensions that Distinguish Vectors.
Journal of Computer and System Sciences, 82(3):521–535, 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

Conference Publications 2015

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
René van Bevern and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge and Toby Walsh.
H-Index Manipulation by Merging Articles: Models, Theory, and Experiments.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI '15), pages 808–814. AAAI Press, 2015.
Bibtex entry Link to publication
René van Bevern and Christian Komusiewicz and Manuel Sorge.
Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems.
In Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS '15), pages 130–143. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Piotr Skowron and Nimrod Talmon.
Elections with Few Candidates: Prices, Weights, and Covering Problems.
In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT '15), pages 414–431. Springer, 2015.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon.
Large-Scale Election Campaigns: Combinatorial Shift Bribery.
In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '15), pages 67–75. ACM, 2015.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Rolf Niedermeier and Toby Walsh.
Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI '15), pages 164–170. AAAI Press, 2015.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Vincent Froese and Nimrod Talmon.
Multi-Player Diffusion Games on Graph Classes.
In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC '15), pages 200–211. Springer, 2015. Full version available at http://arxiv.org/abs/1412.2544.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Stefan Fafianie and Vincent Froese and Rolf Niedermeier and Nimrod Talmon.
The Complexity of Finding Effectors.
In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC '15), pages 224–235. Springer, 2015. Full version available at http://arxiv.org/abs/1411.7838.
Bibtex entry Link to publication
Link to original publication
Jiehua Chen and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon.
Elections with Few Voters: Candidate Control Can Be Easy.
In Proceedings of the 29th Conference on Artificial Intelligence (AAAI '15), pages 2045–2051. AAAI Press, 2015.
Bibtex entry Link to publication
Link to original publication
Till Fluschnik and Stefan Kratsch and Rolf Niedermeier and Manuel Sorge.
The Parameterized Complexity of the Minimum Shared Edges Problem.
In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS '15), pages 448–462. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
Bibtex entry Link to publication
Link to original publication
Archontia C. Giannopoulou and George B. Mertzios and Rolf Niedermeier.
Polynomial Fixed-parameter Algorithms: {A} Case Study for Longest Path on Interval Graphs.
In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC '15), pages 102–113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
Bibtex entry Link to publication
Sepp Hartung and Holger H. Hoos.
Programming by Optimisation meets Parameterised Algorithmics: A Case Study for Cluster Editing.
In Proceedings of the 9th Learning and Intelligent OptimizatioN Conference (LION'15), pages 43–58. Springer, 2015.
Bibtex entry Link to publication
Link to original publication
Sepp Hartung and Nimrod Talmon.
The Complexity of Degree Anonymization by Graph Contractions.
In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC '15), pages 260–271. Springer, 2015.
Bibtex entry Link to publication
Falk Hüffner and Christian Komusiewicz and Manuel Sorge.
Finding Highly Connected Subgraphs.
In Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'15), pages 254–265. Springer, 2015.
Bibtex entry Link to publication
Link to original publication
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
Christian Komusiewicz and Manuel Sorge and Kolja Stahl.
Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments.
In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA '15), pages 82-93. Springer, 2015.
Bibtex entry Link to publication
Christian Komusiewicz and Andreea Radulescu.
On the Sound Covering Cycle Problem in Paired de Bruijn Graphs.
In Proceedings of the 9th International Frontiers of Algorithmics Workshop (FAW'15), pages 150–161. 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
Stefan Kratsch and Manuel Sorge.
On Kernelization and Approximation for the Vector Connectivity Problem.
In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC '15), pages 377–388. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
Bibtex entry Link to publication
Link to original publication
Nimrod Talmon.
Privacy in Elections: k-Anonymizing Preference Orders.
In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT '15), pages 299–310. Springer, 2015.
Bibtex entry Link to publication
Link to original publication

Journal Publications 2015

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.
ACM Transactions on Economics and Computation, 4(1):5:1–5:28, 2015.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Matthias Mnich and Rolf Niedermeier and Mathias Weller.
Interval scheduling and colorful independent sets.
Journal of Scheduling, 18(5):449–469, 2015.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Andreas Emil Feldmann and Manuel Sorge and Ondrej Suchý.
On the Parameterized Complexity of Computing Balanced Partitions in Graphs.
Theory of Computing Systems, 57:1–35, Springer, 2014.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Jiehua Chen and Falk Hüffner and Stefan Kratsch and Nimrod Talmon and Gerhard J. Woeginger.
Approximability and parameterized complexity of multicover by c-intervals.
Information Processing Letters, 2015. In press.
Bibtex entry Link to publication
Link to original publication
René van Bevern and Rodney G. Downey and Michael R. Fellows and Serge Gaspers and Frances A. Rosamond.
Myhill-Nerode methods for hypergraphs.
Algorithmica In press
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 Vertex Dissolution.
SIAM Journal on Discrete Mathematics, 29(2):888–914, 2015.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Nimrod Talmon.
NP-Hardness of Two Edge Cover Generalizations with Applications to Control and Bribery for Approval Voting.
Information Processing Letters, Elsevier, 2015. In press.
Bibtex entry Link to 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.
Theoretical Computer Science, 607(1):16–34, Elsevier, 2015.
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.
Journal of Computer and System Sciences, 81(4):766-782, Elsevier, 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
Sharon Bruckner and Falk Hüffner and Christian Komusiewicz.
A Graph Modification Approach for Finding Core–Periphery Structures in Protein Interaction Networks.
Algorithms for Molecular Biology, 2015.
Bibtex entry Link to publication
Laurent Bulteau and Jiehua Chen and Piotr Faliszewski and Rolf Niedermeier and Nimrod Talmon.
Combinatorial Voter Control in Elections.
Theoretical Computer Science, 589:99–120, 2015.
Bibtex entry
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, 29(1):1–25, 2015.
Bibtex entry Link to publication
Link to original publication
Guillaume Fertin and Shahrad Jamshidi and Christian Komusiewicz.
Towards an Algorithmic Guide to Spiral Galaxies.
Theoretical Computer Science, 586:26-39, 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
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
Falk Hüffner and Christian Komusiewicz and Rolf Niedermeier and Martin Rötzschke.
The Parameterized Complexity of the Rainbow Subgraph Problem.
Algorithms, 8(1):60-81, 2015.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and Manuel Sorge.
An Algorithmic Framework for Fixed-Cardinality Optimization in Sparse Graphs Applied to Dense Subgraph Problems.
Discrete Applied Mathematics, 193:145-161, Elsevier, 2015.
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.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2014

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
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
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
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
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
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
Sharon Bruckner and Falk Hüffner and Christian Komusiewicz.
A Graph Modification Approach for Finding Core–Periphery Structures in Protein Interaction Networks.
In Proceedings of the 14th Workshop on Algorithms in Bioinformatics (WABI '14), pages 340–351. Springer, 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 '14), pages 298–309. Springer, 2014.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Christian Komusiewicz.
Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable.
In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '14), pages 102-121. SIAM, 2014.
Bibtex entry Link to publication
Link to original publication
Laurent Bulteau and Guillaume Fertin and Christian Komusiewicz.
Reversal Distances for Strings with Few Blocks or Small Alphabets.
In Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM '14), pages 50-59. 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), pages 153–164. 2014.
Bibtex entry Link to publication
Yann Disser and Stefan Kratsch and Manuel Sorge.
The Minimum Feasible Tileset problem.
In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA '14), pages 144–155. Springer, 2014.
Bibtex entry Link to publication
Link to original publication
Guillaume Fertin and Shahrad Jamshidi and Christian Komusiewicz.
Towards an Algorithmic Guide to Spiral Galaxies.
In Proceedings of the Seventh International Conference on Fun with Algorithms (FUN'14), pages 50-59. 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
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
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

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
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
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
René van Bevern.
Towards Optimal and Expressive Kernelization for $d$-Hitting Set.
Algorithmica, 70(1):129-147, 2014.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Piotr Faliszewski and Jiong Guo and Rolf Niedermeier and Gerhard J. Woeginger.
Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges.
Tsinghua Science and Technology, 19(4):358-373, 2014.
Bibtex entry Link to publication
Link to original publication
Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondřej Suchý and Gerhard J. Woeginger.
A multivariate complexity analysis of lobbying in multiple referenda.
Journal of Artificial Intelligence Research, 50:409–446, 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
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
Martin Dörnfelder and Jiong Guo and Christian Komusiewicz and Mathias Weller.
On the parameterized complexity of consensus clustering.
Theoretical Computer Science, 542:71-82, 2014.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Danny Hermelin and Christian Komusiewicz.
Local search for string problems: Brute-force is essentially optimal.
Theoretical Computer Science, 525:30-41, 2014.
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.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(3):455-467, 2014.
Bibtex entry Link to publication
Link to original publication
Christian Komusiewicz and Johannes Uhlmann.
A Cubic-Vertex Kernel for Flip-Consensus Tree.
Algorithmica, 68(1):81–108, Springer, 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

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. Springer, 2013.
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.
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
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
René van Bevern and Michael R. Fellows and Serge Gaspers and Frances A. Rosamond.
Myhill-Nerode Methods for Hypergraphs.
In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13), pages 372-382. 2013.
Bibtex entry Link to publication
René van Bevern and Andreas Emil Feldmann and Manuel Sorge and Ondrej Suchý.
On the Parameterized Complexity of Computing Graph Bisections.
In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '13), pages 76–88. 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. Springer, 2013.
Bibtex entry Link to publication
Robert Bredereck and Jiehua Chen and Gerhard J. Woeginger.
Are There Any Nicely Structured Preference Profiles Nearby?.
In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI '13), pages 62-68. AAAI Press, 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 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
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
Laurent Bulteau and Guillaume Fertin and Christian Komusiewicz and Irena Rusu.
A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications.
In Proceedings of the 13th Workshop on Algorithms in Bioinformatics (WABI '13), pages 244-258. 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
Jiong Guo and Danny Hermelin and Christian Komusiewicz.
Local Search for String Problems: Brute Force is Essentially Optimal.
In Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching (CPM '13), pages 130-141. 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
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
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 Jiehua Chen and Gerhard J. Woeginger.
A characterization of the single-crossing domain.
Social Choice and Welfare, 41(4):989-998, 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
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
Neeldhara Misra and Hannes Moser and Venkatesh Raman and Saket Saurabh and Somnath Sikdar.
The Parameterized Complexity of Unique Coverage and Its Variants.
Algorithmica, 65(3):517-544, Springer, 2013.
Bibtex entry
Link to original 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
Johannes Uhlmann and Mathias Weller.
Two-Layer Planarization parameterized by feedback edge set.
Theoretical Computer Science, 494:99 - 111, 2013.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2012

René van Bevern.
Towards Optimal and Expressive Kernelization for d-Hitting Set.
In Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON'12), pages 121–132. Springer, 2012.
Bibtex entry Link to publication
Link to original publication
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 AAAI 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
Leo Brueggeman and Michael R. Fellows and Rudolf Fleischer and Martin Lackner and Christian Komusiewicz and Yiannis Koutis and Andreas Pfandler and Frances Rosamond.
Train Marshalling is Fixed Parameter Tractable.
In Proceedings of the 6th International Conference on Fun with Algorithms (FUN '12), pages 51-56. 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
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
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
Christian Komusiewicz and Manuel Sorge.
Finding Dense Subgraphs of Sparse Graphs.
In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC'12), pages 242–251. 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
Christian Komusiewicz and Johannes Uhlmann.
Cluster Editing with Locally Bounded Modifications.
Discrete Applied Mathematics, 160(15):2259-2270, Elsevier, 2012.
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
Christoph Schmidt and Thomas Weiss and Christian Komusiewicz and Herbert Witte and Lutz Leistritz.
An Analytical Approach to Network Motif Detection in Samples of Networks with Pairwise Different Vertex Labels.
Computational and Mathematical Methods in Medicine, 2012. Article ID 910380
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 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
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
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.
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
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
Martin Dörnfelder and Jiong Guo and Christian Komusiewicz and Mathias Weller.
On the Parameterized Complexity of Consensus Clustering.
In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC '11), pages 624-633. 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
Christian Komusiewicz and Johannes Uhlmann.
Alternative Parameterizations for Cluster Editing.
In Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '11), pages 344-355. 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
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

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 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
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
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
Jiong Guo and Iyad A. Kanj and Christian Komusiewicz and Johannes Uhlmann.
Editing Graphs into Disjoint Unions of Dense Clusters.
Algorithmica, 1–22, Springer, 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

Yoram Bachrach and Nadja Betzler and Piotr Faliszewski.
Probabilistic Possible Winner Determination.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI '10), AAAI Press, 2010.
Bibtex entry Link to publication
Link to original publication
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
Nadja Betzler.
On Problem Kernels for Possible Winner Determination under the k-Approval Protocol.
In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS '10), pages 114–125. 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
Johannes Uhlmann and Mathias Weller.
Two-Layer Planarization Parameterized by Feedback Edge Set.
In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC '10), pages 431–442. Springer, 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
Nadja Betzler and Britta Dorn.
Towards a dichotomy for the Possible Winner problem in elections based on scoring rules.
Journal of Computer and System Sciences, 76(8):812–836, 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 Johannes Uhlmann.
Kernelization and complexity results for connectivity augmentation problems.
Networks, 56(2):131–142, 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
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
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 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
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 Britta Dorn.
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules.
In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS '09), pages 124–136. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Daniel Brügmann and Christian Komusiewicz and Hannes Moser.
On Generating Triangle-Free Graphs.
In Proceedings of the DIMAP Workshop on Algorithmic Graph Theory (AGT '09), pages 51–58. Elsevier, 2009.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Daniel Lokshtanov and Saket Saurabh.
Incompressibility through Colors and {ID}s.
In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP '09), pages 378–389. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Michael R. Fellows and Frances A. Rosamond.
Parameterized Complexity of Stabbing Rectangles and Squares in the Plane.
In Proceedings of the 3rd International Workshop on Algorithms and Computation (WALCOM '09), pages 298–309. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Rosa Enciso and Michael R. Fellows and Jiong Guo and Iyad A. Kanj and Frances A. Rosamond and Ondrej Suchý.
What Makes Equitable Connected Partition Easy.
In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC '09), pages 122–133. Springer, 2009.
Bibtex entry
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
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 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 Iyad A. Kanj.
The Parameterized Complexity of Some Minimum Label Problems.
In Proceedings of the 35th International Workshop an Graph-Theoretic Concepts in Computer Science (WG '09), pages 88–99. 2009.
Bibtex entry
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
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 Iyad A. Kanj and Christian Komusiewicz and Johannes Uhlmann.
Editing Graphs into Disjoint Unions of Dense Clusters.
In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC '09), pages 583–593. Springer, 2009.
Bibtex entry Link to publication
Link to original publication
Jiong Guo.
Fixed-Parameter Algorithms for Graph-Modeled Data Clustering.
In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC '09), pages 39–48. Springer, 2009.
Bibtex entry Link to publication
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
Hannes Moser.
A Problem Kernelization for Graph Packing.
In Proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '09), pages 401–412. 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 Johannes Uhlmann.
Parameterized complexity of candidate control in elections and related digraph problems.
Theoretical Computer Science, 410(52):5425–5442, 2009.
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 rankings.
Theoretical Computer Science, 410(45):4554–4570, 2009.
Bibtex entry Link to publication
Link to original publication
Michael Dom.
Algorithmic Aspects of the Consecutive-Ones Property.
Bulletin of the European Association for Theoretical Computer Science, 98:27–59, EATCS, 2009.
Bibtex entry Link to publication
Link to original publication
Jens Gramm and Tzvika Hartman and Till Nierhoff and Roded Sharan and Till Tantau.
On the complexity of SNP block partitioning under the perfect phylogeny model.
Discrete Mathematics, 309(18):5610–5617, 2009.
Bibtex entry
Link to original publication
Jiong Guo.
A more effective linear kernelization for cluster editing.
Theoretical Computer Science, 410(8-10):718–726, 2009.
Bibtex entry
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
Falk Hüffner.
Algorithm Engineering for Optimal Graph Bipartization.
Journal of Graph Algorithms and Applications, 13(2):77–98, 2009.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner.
{Parametrisierte Ans\"atze f\"ur schwere Graphprobleme: Algorithmen und Experimente}.
it – Information Technology, 51(3):171–174, 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
Hannes Moser and Dimitrios M. Thilikos.
Parameterized Complexity of Finding Regular Induced Subgraphs.
Journal of Discrete Algorithms, 7(2):181–190, Elsevier, 2009.
Bibtex entry Link to publication
Link to original publication
Hannes Moser and Somnath Sikdar.
The Parameterized Complexity of the Induced Matching Problem.
Discrete Applied Mathematics, 157(4):715–727, Elsevier, 2009.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2008

Nadja Betzler and Johannes Uhlmann.
Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems.
In Proceedings of the Second International Conference on Combinatorial Optimization and Applications (COCOA '08), pages 43–53. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
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
Michael Dom and Somnath Sikdar.
The Parameterized Complexity of the Rectangle Stabbing Problem and its Variants.
In Proceedings of the 2nd International Frontiers of Algorithmics Workshop (FAW '08), pages 288–299. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Michael Dom and Daniel Lokshtanov and Saket Saurabh and Yngve Villanger.
Capacitated Domination and Covering: A Parameterized Perspective.
In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC '08), pages 78–90. Springer, 2008.
Bibtex entry Link to publication
Link to original publication
Jiong Guo and Falk Hüffner and Christian Komusiewicz and Yong Zhang.
Improved Algorithms for Bicluster Editing.
In Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation (TAMC '08), pages 451–462. Springer, 2008. After publication, we have been notified of a problem in the proof of Theorem 4 that does not seem to be easy to fix. Thus, we retract the results in Section 4.
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
Christian Komusiewicz and Johannes Uhlmann.
A Cubic-Vertex Kernel for Flip-Consensus Tree.
In Proceedings of the 28th Foundations of Software Technology and Theoretical Computer Science Conference (FSTTCS '08), pages 280–291. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 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
Stefan Eckhardt and Sven Kosub and Moritz G. Maaß and Hanjo Täubig and Sebastian Wernicke.
Combinatorial network abstraction by trees and distances.
Theoretical Computer Science, 407(1-3):1–20, 2008.
Bibtex entry
Link to original publication
Jens Gramm and Arfst Nickelsen and Till Tantau.
Fixed-Parameter Algorithms in Phylogenetics.
The Computer Journal, 51(1):79–101, 2008.
Bibtex entry
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 Sebastian Wernicke and Thomas Zichner.
Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection.
Algorithmica, 52(2):114–132, 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 Johannes Uhlmann.
Kernelization and Complexity Results for Connectivity Augmentation Problems.
In Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS '07), pages 483–494. 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
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.
A More Effective Linear Kernelization for Cluster Editing.
In Proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE '07), pages 36–47. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Jiong Guo.
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs.
In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC '07), pages 915–926. Springer, 2007.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Sebastian Wernicke and Thomas Zichner.
Algorithm Engineering for Color-Coding to Facilitate Signaling Pathway Detection.
In Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC '07), pages 277–286. Imperial College Press, 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
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

Journal Publications 2007

Jens Gramm and Till Nierhoff and Roded Sharan and Till Tantau.
Haplotyping with missing data via perfect path phylogenies.
Discrete Applied Mathematics, 155(6-7):788–805, 2007.
Bibtex entry Link to publication
Link to original publication
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
Jiong Guo and Falk Hüffner and Hannes Moser.
Feedback Arc Set in Bipartite Tournaments is NP-Complete.
Information Processing Letters, 102(2–3):62–65, 2007.
Bibtex entry Link to publication
Link to original publication
Falk Hüffner and Sebastian Wernicke and Thomas Zichner.
{FASPAD}: fast signaling pathway detection.
Bioinformatics, 23(13):1708–1709, 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
Sebastian Wernicke and Florian Rasche.
Simple and fast alignment of metabolic pathways by exploiting local diversity.
Bioinformatics, 23(15):1978–1985, 2007.
Bibtex entry Link to publication
Link to original publication

Conference Publications 2006

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
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
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 Tzvika Hartman and Till Nierhoff and Roded Sharan and Till Tantau.
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
In Proceedings of the 6th International Workshop on Algorithms in Bioinformatics (WABI '06), pages 92–102. 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
Hannes Moser and Dimitrios M. Thilikos.
Parameterized Complexity of Finding Regular Induced Subgraphs.
In Proceedings of the 2nd Algorithms and Complexity in Durham Workshop (ACiD '06), pages 107–118. College Publications, 2006.
Bibtex entry Link to publication
Harald Sack and Uwe Krüger and Michael Dom.
A Knowledge Base on {NP}-complete Decision Problems and its Application in Bibliographic Search.
In XML-Tage 2006, 2006.
Bibtex entry Link to 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 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
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
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
Sebastian Wernicke and Florian Rasche.
FANMOD: a tool for fast network motif detection.
Bioinformatics, 22(9):1152–1153, 2006.
Bibtex entry
Link to original publication
Sebastian Wernicke.
Efficient Detection of Network Motifs.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):347–359, 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
Stefan Eckhardt and Sven Kosub and Moritz G. Maaß and Hanjo Täubig and Sebastian Wernicke.
Combinatorial Network Abstraction by Trees and Distances.
pages 1100–1109. 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
Falk Hüffner.
Algorithm Engineering for Optimal Graph Bipartization.
In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA '05), pages 240–252. Springer, 2005.
Bibtex entry Link to publication
Link to original publication
Sebastian Wernicke.
A Faster Algorithm for Detecting Network Motifs.
In Proceedings of the 5th International Workshop, on Algorithms in Bioinformatics (WABI '05), pages 165–177. 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
Roded Sharan and Jens Gramm and Zohar Yakhini and Amir Ben-Dor.
Multiplexing Schemes for Generic SNP Genotyping Assays.
Journal of Computational Biology, 12(5):514–533, 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
Jens Gramm and Till Nierhoff and Till Tantau.
Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable.
In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC '04), pages 174–186. 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 Jirí Fiala.
Geometric separation and exact solutions for the parameterized independent set problem on disk graphs.
Journal of Algorithms, 52(2):134–151, 2004.
Bibtex entry
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
Jens Gramm.
A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns.
IEEE/ACM Transactions of Computational Biology and Bioinformatics, 1(4):171–180, 2004. An error in the main result of this work as well as the NP-hardness of the considered problem was shown by Shuai Cheng Li and Ming Li [WABI 2006].
Bibtex entry
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 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
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
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 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
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
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 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
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 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
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.
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
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

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

Zusatzinformationen / Extras