Prof. Dr. Rolf Niedermeier

Publications

2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993 and 1992.

The publication list is also available in BibTex format.

2007

Conference Articles

• Michael Dom, Jiong Guo and Rolf Niedermeier: Approximability and parameterized complexity of consecutive ones submatrix problems, Shanghai, China. In Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC'07). Volume 4484 in Lecture Notes in Computer Science, pages 680–691. May 2007, Springer. Featured links: original publication.
• Falk Hüffner, Christian Komusiewicz, Hannes Moster and Rolf Niedermeier: Isolation concepts for enumerating dense subgraphs, Banff, Canada. In Proceedings of the 13th International Computing and Combinatorics Conference (COCOON'07). Volume 4598 in Lecture Notes in Computer Science, pages 140–150. July 2007, Springer. Featured links: original publication.
• Jiong Guo and Rolf Niedermeier: Linear problem kernels for NP-hard problems on planar graphs, Wroclaw, Poland. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07). Volume 4596 in Lecture Notes in Computer Science, pages 375–386. June 2007, Springer.
• Nadja Betzler, Falk Hüffner and Rolf Niedermeier: Optimal edge deletions for signed graph balancing, Rome, Italy. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Volume 4525 in Lecture Notes in Computer Science, pages 297–310. June 2007, Springer. Featured links: original publication, Source code and Objective Caml.
• Jiong Guo and Rolf Niedermeier: Probe matrix problems: totally balanced matrices, Portland, USA. In Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM'07). Volume 4508 in Lecture Notes in Computer Science, pages 368–377. June 2007, Springer. Featured links: original publication.
• Michael Dom and Rolf Niedermeier: The search for consecutive ones submatrices: faster and more general, Durham, England. In Proceedings of the 3rd Workshop on Algorithms and Complexity in Durham (ACiD'07). In Journal of Computer and System Sciences. September 2007, College Publications.

2006

Conference Articles

• Jochen Alber, B. Dorn and Rolf Niedermeier: A general data reduction scheme for domination in graphs, Merin, Czech Republic. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'06). Volume 3831 in Lecture Notes in Computer Science, pages 137–147. January 2006, Springer.
• Jiong Guo, Falk Hüffner, E. Kenar, Rolf Niedermeier and J. Uhlmann: Complexity and exact algorithms for multicut, Merin, Czech Republic. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'06). Volume 3831 in Lecture Notes in Computer Science, pages 303–312. January 2006, Springer.
• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Data reduction, exact, and heuristic algorithms for clique cover, Miami, USA. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). In SIAM, pages 86–94. January 2006. Featured links: original publication.
• Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier and A. Truß: Fixed-parameter tractability results for feedback set problems in tournaments, Rome, Italy. In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC'06). Volume 3998 in Lecture Notes in Computer Science, pages 320–331. May 2006, Springer.
• Jiong Guo, Rolf Niedermeier and Sebastian Wernicke: Fixed-parameter tractability results for full-degree spanning tree and its dual, Zürich, Switzerland. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Volume 4169 in Lecture Notes in Computer Science, pages 203–214. September 2006.
• Jochen Alber, M. Brosemann, Falk Hüffner and Rolf Niedermeier: Matrix robustness, with an application to power system observability, Durham, England. In Proceedings of the 2nd Algorithms and Complexity in Durham (ACiD'06). Volume 7 in Texts in Algorithmics, pages 37–48. September 2006.
• Michael Dom, Jiong Guo, Rolf Niedermeier and Sebastian Wernicke: Minimum membership set covering and the consecutive ones property, Riga, Latvia. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT'06). Volume 4059 in Lecture Notes in Computer Science, pages 339–350. July 2006, Springer.

Journal Articles

• Jiong Guo and Rolf Niedermeier: A fixed-parameter tractability result for multicommodity demand flow in trees. In Information Processing Letters, issue 97(3), pages 109–114. 2006.
• Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier, H.-P. Piepho and R. Schmid: Algorithms for compact letter displays: comparison and evaluation. In Computational Statistics and Data Analysis. Semptember 2006. Accepted for publication.
• Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier and Sebastian Wernicke: Compression-based fixed-parameter algorithms for Feedback Vertex Set and Edge Bipartization. In Journal of Computer and System Sciences, issue 72(8), pages 1368–1396. 2006. Featured links: original publication.
• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Data reduction and exact algorithms for clique cover. In ACM Journal of Experimental Algorithmics. Semptember 2006. Accepted for publication.
• Michael Dom, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Error compensation in leaf power problems. In Algorithmica, issue 44(4), pages 363–381. 2006.
• Jiong Guo and Rolf Niedermeier: Exact algorithms and applications for tree-like weighted set cover. In Journal of Discrete Algorithms, issue 4(4), pages 608–622. 2006. Featured links: original publication.
• Jochen Alber, Nadja Betzler and Rolf Niedermeier: Experiments on data reduction for optimal domination in networks. In Annals of Operations Research, issue 146(1), pages 105–117. 2006.
• Michael R. Fellows, Jens Gramm and Rolf Niedermeier: On the parameterized intractability of motif search problems. In Combinatorica, issue 26(2), pages 141–167. 2006.
• Jens Gramm, Jiong Guo and Rolf Niedermeier: Parameterized Intractability of Distinguishing Substring Selection. In Theory of Computing Systems, issue 39(4), pages 545–560. 2006. Featured links: original publication.
• Jiong Guo, RolF Niedermeier and Sebastian Wernicke: Parameterized complexity of vertex cover variants. In Theory of Computing Systems. February 2006. Accepted for publication.
• Jens Gramm, Jiong Guo and Rolf Niedermeier: Parameterized intractability of distinguishing substring selection. In Theory of Computing Systems, issue 39(4), pages 545–560. 2006.
• Michael R. Fellows, Jens Gramm and Rolf Niedermeier: Parameterized intractability of motif search problems. In Combinatorica, issue 26((2)), pages 141–167. 2006. Featured links: original publication.
• Jens Gramm, Jiong Guo and Rolf Niedermeier: Pattern matching for arc-annotated sequences. In ACM Transactions on Algorithms, issue 2(1), pages 44–65. 2006.
• Jens Gramm, Jiong Guo, Rolf Niedermeier and Sebastian Wernicke: The computational complexity of avoiding forbidden submatrices by row deletions. In International Journal of Foundations of Computer Science, issue 17(6), pages 1467–1484. 2006. Featured links: original publication.
• Nadja Betzler, Rolf Niedermeier and Johannes Uhlmann: Tree decompositions of graphs: saving memory in dynamic programming. In Discrete Optimization, issue 3(3), pages 220–229. 2006.

2005

Conference Articles

• Michael Dom, Jiong Guo and Rolf Niedermeier: Bounded degree closest k-tree power is NP-complete, Kunming, China. In Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05). Volume 3595 in Lecture Notes in Computer Science, pages 757–766. August 2005, Springer. Featured links: original publication.
• Michael Dom, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Extending the tractability border for closest leaf powers, Metz, France. In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005). Volume 3787 in Lecture Notes in Computer Science, pages 397–408. June 2005, Springer. Featured links: original publication.
• Jiong Guo, Rolf Niedermeier and Daniel Raible: Improved algorithms and complexity results for power domination in graphs, Lübeck, Germany. In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05). Volume 3623 in Lecture Notes in Computer Science, pages 172–184. August 2005, Springer. Featured links: original publication.
• Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier and Sebastian Wernicke: Improved fixed-parameter algorithms for two feedback set problems, Waterloo, Canada. In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS'05). Volume 3608 in Lecture Notes in Computer Science, pages 158–168. August 2005, Springer. Featured links: original publication and Journal version.
• Jiong Guo, Rolf Niedermeier and Sebastian Wernicke: Parameterized complexity of generalized vertex cover problems, Waterloo, Canada. In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS'05). Volume 3608 in Lecture Notes in Computer Science, pages 36–48. August 2005, Springer. Featured links: original publication and Journal version.

Journal Articles

• Jiong Guo and Rolf Niedermeier: Fixed-parameter tractability and data reduction for multicut in trees. In Networks, issue 46(3), pages 124–135. 2005. Featured links: original publication.
• Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Frances Rosamond and Ulrike Stege: A refined search tree technique for Dominating Set on planar graphs. In Journal of Computer and System Sciences, issue 71(4), pages 385–405. 2005. Featured links: original publication.
• Jochen Alber, Frederic Dorn and Rolf Niedermeier: Experimental evaluation of a tree decomposition based algorithm for vertex cover on planar graphs. In Discrete Applied Mathematics, issue 145(2), pages 219–231. 2005. Featured links: original publication.
• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Graph-modeled data clustering: fixed-parameter algorithms for clique generation. In Theory of Computing Systems, issue 38(4), pages 373–392. 2005. Featured links: original publication.

2004

Conference Articles

• Jiong Guo, Falk Hüffner and R. Niedermeier: A structural view on parameterizing problems: distance from triviality, Bergen, Norway. In Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2004). Volume 3162 in Lecture Notes in Computer Science, pages 162–173. September 2004, Springer.
• Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier and Sebastian Wernicke: Avoiding forbidden submatrices by row deletions, Merin, Czech Republic. In Proceedings of the 30th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'04). Volume 2932 in Lecture Notes in Computer Science, pages 349–360. January 2004, Springer.
• Michael Dom, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Error compensation in leaf root problems, Hong Kong, China. In Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004). Volume 3341 in Lecture Notes in Computer Science, pages 389–401. 2004, Springer. Featured links: original publication.
• Hans L. Bodlaender, C. M. H. de Figueiredo, M. Gutierrez, Ton Kloks and Rolf Niedermeier: Simple Max-Cut for split-indifference graphs and graphs with few P4's, Angra dos Reis, Rio de Janeiro, Brazil. In Proceedings of the 3rd Workshop on Efficient and Experimental Algorithms (WEA 2004). Volume 3059 in Lecture Notes in Computer Science, pages 87–99. May 2004, Springer.
• Nadja Betzler, Rolf Niedermeier and J. Uhlmann: Tree decompositions of graphs: saving memeory in dynamic programming, Milano, Italy. In Proceedings of the Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW 2004). . May/June 2004.
• Rolf Niedermeier: Ubiquitous parameterization --- invitation to fixed-parameter algorithms, Prague, Czech Republic. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004). Volume 3153 in Lecture Notes in Computer Science, pages 84–103. August 2004, Springer.

Journal Articles

• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Automated generation of search tree algorithms for hard graph modification problems. In Algorithmica, issue 39(4), pages 321–347. 2004.
• Jochen Alber, Jens Gramm, Jiong Guo and Rolf Niedermeier: Computing the similarity of two sequences with nested arc annotations. In Theoretical Computer Science, issue 312(2--3), pages 337–358. 2004.
• Jochen Alber, Henning Fernau and Rolf Niedermeier: Parameterized complexity: exponential speed-up for planar graph problems. In Journal of Algorithms, issue 52, pages 26–56. 2004.
• Jochen Alber, Michael R. Fellows and Rolf Niedermeier: Polynomial time data reduction for Dominating Set. In Journal of the ACM, issue 51(3), pages 363–384. 2004.

Lecture Notes (in German)

• Rolf Niedermeier: Ausgewählte Graphalgorithmen. At Universität Tübingen. February 2004.

2003

(former) Student's work

• Falk Hüffner: Finding optimal solutions to Atomix. At Universität Tübingen (Studienarbeit). January 2003.
• Jens Gramm: Fixed-Parameter Algorithms for the Consensus Analysis of Genomic Sequences. At Universität Tübingen (Ph.D. thesis). July 2003.
• Falk Hüffner: Graph modification problems and automated search tree generation. At Universität Tübingen (Diploma thesis). October 2003.
• Sebastian Wernicke: On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. At Universität Tübingen (Diploma Thesis). September 2003.

Conference Articles

• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Automated generation of search tree algorithms for graph modification problems, Budapest, Hungary. In Proceedings of the 11th European Symposium on Algorithms (ESA 2003). Volume 2832 in Lecture Notes in Computer Science, pages 642–653. September 2003.
• Jochen Alber, Nadja Betzler and Rolf Niedermeier: Experiments on data reduction for optimal domination in networks, Evry/Paris, France. In Proceedings of the International Network Optimization Conference (INOC 2003). , pages 1–6. October 2003. Featured links: original publication.
• Jens Gramm and Rolf Niedermeier: Faster exact solutions for Max2Sat, editors: G. Bongiovanni, G. Gambosi and R. Petereschi, Rome, Italy. In Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC 2000). Volume 1767 in Lecture Notes in Computer Science, pages 174–186. March 2003, Springer.
• Jens Gramm, Jiong Guo, Falk Hüffner and Rolf Niedermeier: Graph-modeled data clustering: fixed-parameter algorithms for clique generation, Rome, Italy. In Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC 2003). Volume 2653 in Lecture Notes in Computer Science, pages 108–119. May 2003.
• Jens Gramm, Jiong Guo and Rolf Niedermeier: On exact and approximation algorithms for Distinguishing Substring Selection, Malmö, Sweden. In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003). Volume 2751 in Lecture Notes in Computer Science, pages 195–209. August 2003.

Journal Articles

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

Ph.D. thesis

• Jochen Alber: Exact Algorithms for NP-hard Problems on Networks: Design, Analysis, and Implementation. At Universität Tübingen. January 2003.

2002

(former) Student's work

• Jiong Guo: Exact algorithms for the Longest Common Subsequence problem for arc-annotated sequences. At Universität Tübingen (Diploma Thesis). February 2002.

Conference Articles

• Jens Gramm and Rolf Niedermeier: Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach, Saarbrücken, Germany. In Proceedings of the European Conference on Computational Biology 2002 (ECCB 2002). Volume 18 (Supplement 2) in Bioinformatics, pages 128–139. October 2002, Oxford University Press.
• Jochen Alber, Michael R. Fellows and Rolf Niedermeier: Efficient data reduction for Dominating Set: a linear problem kernel for the planar case, Turku, Finland. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT'2002). Volume 2368 in Lecture Notes in Computer Science, pages 150–159. July 2002, Springer.
• Jochen Alber and Rolf Niedermeier: Improved tree decomposition based algorithms for domination-like problems, Cancun, Mexico. In Proceedings of the 5th Latin American Theoretical INformatics (LATIN 2002). Volume 2286 in Lecture Notes in Computer Science, pages 613–627. April 2002, Springer.
• Michael R. Fellows, Jens Gramm and Rolf Niedermeier: Parameterized intractability of Closest Substring, editors: H. Alt and A. Ferreira, Antibes Juan-les-Pins, France. In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002). Volume 2285 in Lecture Notes in Computer Science, pages 262–273. March 2002, Springer.
• Jens Gramm, Jiong Guo and Rolf Niedermeier: Pattern matching for arc-annotated sequences, Kanpur, India. In Proceedings of the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2002). Volume 2556 in Lecture Notes in Computer Science, pages 182–193. December 2002.
• Jochen Alber, Jens Gramm, Jiong Guo and Rolf Niedermeier: Towards optimally solving the Longest Common Subsequence problem for sequences with nested arc annotations in linear time, Fukuoka, Japan. In Proceedings of the 13th Annual Symposium on Combinatorial Pattern matching (CPM 2002). Volume 2373 in Lecture Notes in Computer Science, pages 99–114. July 2002.

Conference Posters

• Jens Gramm, Falk Hüffner and Rolf Niedermeier: Closest strings, primer design, and motif search, Washington DC, USA. April 2002. Poster at RECOMB 2002 (6th Annual International Conference on Computational Molecular Biology).

Habilitation thesis

• Rolf Niedermeier: Invitation to fixed-parameter algorithms. In Habilitation thesis, Universität Tübingen. September 2002.

Journal Articles

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

Lecture Notes (in German)

• M. Kaufmann and Rolf Niedermeier: Algorithmen. At Universität Tübingen. July 2002.

Technical Reports

• Michael R. Fellows, Jens Gramm and Rolf Niedermeier: Parameterized Intractability of Motif Search Problems. At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, technical report WSI-2002-2. May 2002.

2001

Conference Articles

• Jens Gramm, Rolf Niedermeier and Peter Rossmanith: Exact solutions for Closest String and related problems, Christchurch, New Zealand. In Proceedings of the 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001). Volume 2223 in Lecture Notes in Computer Science, pages 441–452. December 2001, Springer.
• Stefan Edelkamp, Henning Fernau, Falk Hüffner and Rolf Niedermeier: Finding optimal solutions to Atomix, Vienna, Austria. In Proceedings of the Joint German/Austrian Conference on Artificial Intelligence, 24th German / 9th Austrian Conference on Artificial Intelligence (KI 2001). Volume 2174 in Lecture Notes in AI, pages 229–243. September 2001, Springer.
• Jochen Alber, Henning Fernau and Rolf Niedermeier: Graph separators: a parameterized view, Guilin, China. In Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON 2001). Volume 2108 in Lecture Notes in Computer Science, pages 318–327. August 2001. For the long version see the technical report below.
• Jens Gramm and Rolf Niedermeier: Minimum quartet inconsistency is fixed parameter tractable, editors: A. Amir and G. M. Landau, Jerusalem, Israel. In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001). Volume 2089 in Lecture Notes in Computer Science, pages 241–256. July 2001, Springer.
• Jochen Alber, Henning Fernau and Rolf Niedermeier: Parameterized complexity: Exponential speed-up for planar graph problems, Crete, Greece. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001). Volume 2076 in Lecture Notes in Computer Science, pages 261–272. July 2001. For the long version see the technical report below.
• Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Frances Rosamond and Ulrike Stege: Refined search tree technique for Dominating Set on planar graphs, Marianske Lazne, Czech Republic. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001). Volume 2136 in Lecture Notes in Computer Science, pages 111–122. August 2001, Springer.

Conference Posters

• Jens Gramm and Rolf Niedermeier: Evaluating an algorithm for parameterized Minimum Quartet Inconsistency, Montreal, Canada. April 2001. Poster at RECOMB 2001 (5th Annual International Conference on Computational Molecular Biology).

Journal Articles

• Henning Fernau and Rolf Niedermeier: An efficient exact algorithm for constraint bipartite vertex cover. In Journal of Algorithms, issue 38(2), pages 374–410. 2001.
• Jochen Alber, Jens Gramm and Rolf Niedermeier: Faster exact algorithms for hard problems: a parameterized point of view. In Discrete Mathematics, issue 229(1--3), pages 3–27. 2001.

Technical Reports

• Jochen Alber, Henning Fernau and Rolf Niedermeier: Graph separators: a parameterized view. At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, technical report WSI-2001-8. April 2001. Abstract at COCOON 2001.
• Jochen Alber and Rolf Niedermeier: Improved Tree Decomposition Based Algorithms for Parameterized Planar Dominating Set. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 2001-514. April 2001.
• Jens Gramm and Rolf Niedermeier: Minimum Quartet Inconsistency is fixed parameter tractable. At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, technical report WSI-2001-3. January 2001.
• R. G. Downey, Michael R. Fellows, Rolf Niedermeier and Peter Rossmanith: Parameterized Complexity. At Dagstuhl, technical report NIL. August 2001.
• Jochen Alber, Henning Fernau and Rolf Niedermeier: Parameterized complexity: Exponential speed-up for planar graph problems. At University of Trier, Fed. Rep. of Germany, technical report ECCC TR01-037. March 2001. Abstract at ICALP 2001.

2000

Conference Articles

• Jochen Alber, Hans L. Bodlaender, Henning Fernau and Rolf Niedermeier: Fixed parameter algorithms for Planar Dominating Set and related problems, Bergen, Norway. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT'2000). Volume 1851 in Lecture Notes in Computer Science, pages 97–110. July 2000.
• Rolf Niedermeier and Peter Rossmanith: On efficient fixed parameter algorithms for Weighted Vertex Cover, editors: D. T. Lee Lee and Shang-Hua Teng, Taipei, Taiwan. In Proceedings of the 11th Annual International Symposium on Algorithms And Computation (ISAAC'00). Volume 1969 in Lecture Notes in Computer Science, pages 180–191. December 2000, Springer.

Journal Articles

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

Technical Reports

• Jochen Alber, Hans L. Bodlaender, Henning Fernau and Rolf Niedermeier: Fixed parameter algorithms for Planar Dominating Set and related problems. At Utrecht University, Institute for Information and Computing Sciences, technical report UU-CS-2000-28. September 2000. Abstract at SWAT 2000. Significantly revised version appeared in Algorithmica.
• Jens Gramm, Edward A. Hirsch, Rolf Niedermeier and Peter Rossmanith: New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. At University of Trier, Fed. Rep. of Germany, technical report ECCC TR00-037. 2000. Presented at SAT 2000, Renesse, The Netherlands. Also published in Discrete Applied Mathematics.

1999

(former) Student's work

• Jens Gramm: Exact algorithms for Max2Sat and their applications. At Universität Tübingen. October 1999. Diploma thesis.

Conference Articles

• Henning Fernau and Rolf Niedermeier: An efficient exact algorithm for Constraint Bipartite Vertex Cover, editors: M. Kutylowski, L. Pacholski and T. Wierzbicki, Szklarska Poreba, Poland. In Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science (MFCS'99). Volume 1672 in Lecture Notes in Computer Science, pages 387–397. September 1999, Springer. Long version see TR below.
• Rolf Niedermeier and Peter Rossmanith: New upper bounds for MaxSat, editors: M. Nielsen, J. Wiedermann and P. van Emde Boas, Prague, Czech Republic. In Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP'99). Volume 1644 in Lecture Notes in Computer Science, pages 575–584. July 1999, Springer. Long version see TR below. Journal version above.
• Rolf Niedermeier and Peter Rossmanith: Upper bounds for Vertex Cover further improved, editors: C. Meinel and S. Tison, Trier, Fed. Rep. of Germany. In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS'99). Volume 1563 in Lecture Notes in Computer Science, pages 561–570. March 1999, Springer. Long version see TR below.

Journal Articles

• Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt and Peter Rossmanith: Optimal deterministic sorting and routing on grids and tori with diagonals. In Algorithmica, issue 25, pages 438–42. 1999.

Lecture Notes (in German)

• Jochen Alber and Rolf Niedermeier: Parametrisierte Algorithmen. At Universität Tübingen. September 1999.

Technical Reports

• Rolf Niedermeier and Peter Rossmanith: A general method to speed up fixed-parameter-tractable algorithms. At Technische Universität München, Institut für Informatik, technical report TUM-I9913. June 1999. Revised version appeared in Information Processing Letters.
• Henning Fernau and Rolf Niedermeier: An efficient exact algorithm for Constraint Bipartite Vertex Cover. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 99-424. March 1999. Abstract at MFCS'99. Revised version appearred in Journal of Algorithms.
• Rolf Niedermeier and Peter Rossmanith: An efficient fixed parameter algorithm for 3-Hitting Set. At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, technical report WSI-99-18. October 1999. Revised version in Journal of Discrete Algorithms.

1998

Conference Articles

• Jochen Alber and Rolf Niedermeier: On multi-dimensional Hilbert indexings, Taipei, Taiwan. In Proceedings of the 4th International Computing and Combinatorics Conference (COCOON'98). Volume 1449 in Lecture Notes in Computer Science, pages 329–338. August 1998, Springer. For the long version see the technical report below. The Journal version is above.
• Rolf Niedermeier: Some prospects for efficient fixed parameter algorithms, Jasna, Slovakia. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'98). Volume 1521 in Lecture Notes in Computer Science, pages 168–185. November 1998, Springer. Long version see TR below.

Journal Articles

• Rolf Niedermeier and Peter Rossmanith: Unambiguous computations and locally definable acceptance types. In Theoretical Computer Science, issue 194, pages 137–161. 1998.

Technical Reports

• Klaus-Jörn Lange and Rolf Niedermeier: Data-independence or read, write, and control structures in PRAM computations. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 98-393. May 1998. Revised version in Journal of Computer and System Sciences.
• Rolf Niedermeier and Peter Rossmanith: New upper bounds for MaxSat. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 98-401. July 1998. Revised version appeared in Journal of Algorithms.
• Jochen Alber and Rolf Niedermeier: On multi-dimensional Hilbert indexings. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 98-392. May 1998. Revised version appeared in Theory of Computing Systems.
• Rolf Niedermeier: Some prospects for efficient fixed parameter algorithms. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 98-403. October 1998. Slightly shorter version at SOFSEM'98.
• Rolf Niedermeier and Peter Rossmanith: Upper bounds for vertex cover further improved. At Charles University, Praha, Faculty of Mathematics and Physics, technical report KAM-DIMATIA 98-411. November 1998. Abstract at STACS'99.

1997

(former) Student's work (in German)

• Jochen Alber: Lokalitätseigenschaften diskreter raumfüllender Kurven: Informatik-relevante Ergebnisse. At Universität Tübingen. July 1997. Studienarbeit.

Conference Articles

• Rolf Niedermeier, Klaus Reinhardt and Peter Sanders: Towards optimal locality in mesh-indexings, Krakow, Poland. In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory. Volume 1279 in Lecture Notes in Computer Science, pages 364–375. September 1997, Springer. Long version see TR below. Journal version above.

Lecture Notes (in German)

• Klaus-Jörn Lange: Komplexitätstheorie, editors: B. Jenner and R. Niedermeier. At Universität Tübingen. September 1997.
• Rolf Niedermeier: Randomisierte Algorithmen. At Universität Tübingen. July 1997.

Manuscripts

• Henning Fernau, Klaus-Jörn Lange and Rolf Niedermeier: A remark on parameterized parallel complexity. At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik. March 1997.

Technical Reports

• Rolf Niedermeier, Klaus Reinhardt and Peter Sanders: Towards optimal locality in mesh-indexings. At Universität Karlsruhe, Fakultät für Informatik, technical report IB 12/97. September 1997. Revised and expanded version of the FCT'97 paper. Revised version appeared in Discrete Applied Mathematics.

1996

Conference Articles

• Rolf Niedermeier: Recursively divisible problems, editors: T. Asano, Y. Igarashi, S. Miyano, H. Nagamochi and S. Suri, Osaka, Japan. In Proceedings of the 7th International Symposium on Algorithms and Computation. Volume 1178 in Lecture Notes in Computer Science, pages 83–192. December 1996, Springer.

Ph.D. Thesis

• Rolf Niedermeier: Towards realistic and simple models of parallel computation. At Universität Tübingen. July 1996.

Technical Reports

• Rolf Niedermeier and Peter Sanders: On the Manhattan-distance between points on space-filling mesh-indexings. At Universität Karlsruhe, Fakultät für Informatik, technical report IB 18/96. May 1996.
• Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt and Peter Rossmanith: Optimal deterministic sorting and routing on grids and tori with diagonals. At Technische Universität München, Institut für Informatik, technical report TUM-I9629. July 1996. Revised version appeared in Algorithmica.
• Rolf Niedermeier and Peter Rossmanith: Unambiguous computations and locally definable acceptance types (Expanded Version). At Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, technical report WSI-96-25. August 1996. Shorter version appeared in Theoretical Computer Science.

1995

Conference Articles

• Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt and Peter Rossmanith: Optimal average case sorting on arrays, editors: E. W. Mayr and C. Puech, München, Fed. Rep. of Germany. In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science. Volume 900 in Lecture Notes in Computer Science, pages 503–514. 1995, Springer.
• Rolf Niedermeier and Peter Rossmanith: PRAM's towards realistc parallelism: BRAM's, editor: H. Reichel, Dresden, Fed. Rep. of Germany. In Proceedings of the 10th International Conference on Fundamentals of Computation Theory. Volume 965 in Lecture Notes in Computer Science, pages 363–373. August 1995, Springer.

Journal Articles

• Rolf Niedermeier and Peter Rossmanith: On optimal OROW-PRAM algorithms for computing recursively defined functions. In Parallel Processing Letters, issue 5(2), pages 299–309. June 1995.
• Rolf Niedermeier and Peter Rossmanith: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. In Information and Computation, issue 118(2), pages 227–245. May 1995.

1994

Conference Articles

• Manfred Kunde, Rolf Niedermeier and Peter Rossmanith: Faster sorting and routing on grids with diagonals, editors: P. Enjalbert, E. W. Mayr and K. W. Wagner, Caen, France. In Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science. Volume 775 in Lecture Notes in Computer Science, pages 225–236. 1994, Springer.

1993

Conference Articles

• Klaus-Jörn Lange and Rolf Niedermeier: Data-independences of parallel random access machines, editor: R. K. Shymasundar, Bombay, India. In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science. Volume 761 in Lecture Notes in Computer Science, pages 104–113. December 1993, Springer. Long version see TR below. Journal version above.
• Rolf Niedermeier and Peter Rossmanith: Extended locally definable acceptance types, editors: P. Enjalbert, A. Finkel and K. W. Wagner, Würzburg, Germany. In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science. Volume 665 in Lecture Notes in Computer Science, pages 473–483. 1993, Springer. Long version see TR below. Journal version above.
• Rolf Niedermeier and Peter Rossmanith: On the power of reading and writing simultaneously in parallel computations, editors: N. V. Balasubramanian, F. Y. L. Chin, K. W. Ng and P. Raghavan, Hong Kong. In Proceedings of the 4th International Symposium on Algorithms and Computation. Volume 762 in Lecture Notes in Computer Science, pages 240–249. December 1993, Springer.

1992

Conference Articles

• Rolf Niedermeier and Peter Rossmanith: Unambiguous simulations of auxiliary pushdown automata and circuits, editor: I. Simon, São Paulo, Brazil. In Proceedings of the 1st Symposium on Latin American Theoretical Informatics. Volume 583 in Lecture Notes in Computer Science, pages 387–400. April 1992, Springer.