Articles in Journals

• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  A bound on the pathwidth of sparse graphs with applications to exact algorithms.
  SIAM Journal on Discrete Mathematics, 23(1):407-427, 2009.
• J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S. Sze, and F. Zhang.
  Randomized divide-and-conquer: Improved path, matching, and packing algorithms.
  SIAM Journal on Computing, 2009. to appear.
• D. Mölle, S. Richter, and P. Rossmanith.
  Enumerate and expand: Improved algorithms for connected vertex cover and tree cover.
  Theory of Computing Systems, 43(2):234-253, 2008.
  DOI, BibTeX.
• H. J. Böckenhauer, J. Hromkovič, R. Královic, T. Mömke, and P. Rossmanith.
  Reoptimization of steiner trees: Changing the terminal set.
  Theoretical Computer Science, 2008. to appear.
• B. Fuchs, W. Kern, D. Mölle, S. Richter, P. Rossmanith, and X. Wang.
  Dynamic programming for minimum steiner trees.
  Theory of Computing Systems, 41(3):493-500, 2007.
  Preprint, DOI, BibTeX.
• H.-J. Böckenhauer, J. Hromkovič, J. Kneis, and J. Kupke.
  The parameterized approximability of TSP with deadlines.
  Theory of Computing Systems, 41(3):431-444, 2007.
  DOI, BibTeX.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  Parameterized power domination complexity.
  Information Processing Letters, 98(4):145-149, 2006.
  DOI, BibTeX.
• R. Niedermeier and P. Rossmanith.
  On efficient fixed parameter algorithms for Weighted Vertex Cover.
  Journal of Algorithms, 47:63-77, 2003.
  Preprint, DOI, BibTeX.
• R. Niedermeier and P. Rossmanith.
  An efficient fixed parameter algorithm for 3-hitting set.
  Journal of Discrete Algorithms, 1:89-102, 2003.
  Preprint, DOI, BibTeX.
• J. Gramm, R. Niedermeier, and P. Rossmanith.
  Fixed-parameter algorithms for closest string and related problems.
  Algorithmica, 37(1):25-42, 2003.
  Preprint, DOI, BibTeX.
• J. Gramm, E. A. Hirsch, R. Niedermeier, and P. Rossmanith.
  New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT.
  Discrete Applied Mathematics, 130(2):139-155, 2003.
  Preprint, DOI, BibTeX.
• P. Rossmanith and T. Zeugmann.
  Stochastic finite learning of the pattern languages.
  Machine Learning, 44(1/2):67-91, 2001.
  Preprint.
• T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.
  Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.
  Theoretical Computer Science, 261:119-156, 2001.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  New upper bounds for maximum satisfiability.
  Journal of Algorithms, 36:63-88, 2000.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  A general method to speed up fixed-parameter-tractable algorithms.
  Information Processing Letters, 73:125-129, 2000.
  Preprint.
• J. Esparza, P. Rossmanith, and S. Schwoon.
  A uniform framework for problems on context-free grammars.
  EATCS Bulletin, 72:169-177, October 2000.
  Preprint.
• A. Bouajjani, J. Esparza, A. Finkel, O. Maler, P. Rossmanith, B. Willems, and P. Wolper.
  An efficient automata approach to some problems on context-free grammars.
  Information Processing Letters, 74(5-6):221-227, 2000.
  Preprint.
• M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.
  Optimal deterministic sorting and routing on grids and tori with diagonals.
  Algorithmica, (25):438-458, 1999.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Unambiguous computations and locally definable acceptance types.
  Theoretical Computer Science, (194):137-161, 1998.
  Preprint.
• C. Damm, M. Holzer, and P. Rossmanith.
  Expressing uniformity via oracles.
  Theory of Computing Systems, 30:355-366, 1997.
  Preprint.
• M. Holzer and P. Rossmanith.
  A simpler grammar for Fibonacci numbers.
  The Fibonacci Quarterly, 34(5):465-466, November 1996.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits.
  Information and Computation, 118(2):227-245, May 1995.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  On optimal OROW-PRAM algorithms for computing recursively defined functions.
  Parallel Processing Letters, 5(2):299-309, June 1995.
  Preprint.
• P. Rossmanith and W. Rytter.
  Observations on time parallel recognition of unambiguous context-free languages.
  Information Processing Letters, 44:267-272, 1992.
  Preprint.

Contributions in Refereed Conference Proceedings

• D. Kesdogan, D. Mölle, S. Richter, and P. Rossmanith.
  Breaking anonymity by learning a unique minimum hitting set.
  In Proceedings of the 4th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science. Springer, 2009. to appear.
• J. Kneis, A. Langer, and P. Rossmanith.
  A new algorithm for finding trees with many leaves.
  In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), number 5369 in Lecture Notes in Computer Science, pages 270-281. Springer, 2008.
  DOI, BibTeX.
• J. Kneis, A. Langer, and P. Rossmanith.
  Improved upper bounds for partial vertex cover.
  In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 5344 in Lecture Notes in Computer Science, pages 240-251. Springer, 2008.
  DOI, BibTeX.
• J. Kneis and A. Langer.
  A practical approach to Courcelle's Theorem.
  In Proceedings of the 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS), pages 99-106. Z. Novotný, 2008.
• M.-S. Chang, C.-C. Lin, and P. Rossmanith.
  New fixed-parameter algorithms for the minimum quartet inconsistency problem.
  In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC), number 5018 in Lecture Notes in Computer Science, pages 66-77. Springer, 2008.
  DOI, BibTeX.
• J. Kneis, D. Mölle, and P. Rossmanith.
  Partial vs. complete domination: t-dominating set.
  In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), number 4362 in Lecture Notes in Computer Science, pages 367-376. Springer, 2007.
  DOI, BibTeX.
• D. Mölle, S. Richter, and P. Rossmanith.
  A faster algorithm for the Steiner tree problem.
  In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), number 3884 in Lecture Notes in Computer Science, pages 561-570. Springer, 2006.
  DOI, BibTeX.
• D. Mölle, S. Richter, and P. Rossmanith.
  Enumerate and expand: New runtime bounds for vertex cover variants.
  In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON), number 4112 in Lecture Notes in Computer Science, pages 265-273. Springer, 2006.
  DOI, BibTeX.
• D. Mölle, S. Richter, and P. Rossmanith.
  Enumerate and expand: Improved algorithms for connected vertex cover and tree cover.
  In Proceedings of the 1st International Computer Science Symposium in Russia (CSR), number 3967 in Lecture Notes in Computer Science, pages 270-280. Springer, 2006.
  DOI, BibTeX.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  Intuitive algorithms and t-vertex cover.
  In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), number 4288 in Lecture Notes in Computer Science, pages 598-607. Springer, 2006.
  DOI, BibTeX.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  Divide-and-color.
  In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 4271 in Lecture Notes in Computer Science, pages 58-67. Springer, 2006.
  DOI, BibTeX.
• H.-J. Böckenhauer, L. Forlizzi, J. Hromkovič, J. Kneis, J. Kupke, G. Proietti, and P. Widmayer.
  Reusing optimal TSP solutions for locally modified input instances.
  In G. Navarro, L. E. Bertossi, and Y. Kohayakawa, editors, TCS 2006, IFIP 19th World Computer Congress, volume 209 of IFIP, pages 251-270. Springer, 2006.
  DOI, BibTeX.
• H.-J. Böckenhauer, J. Hromkovič, J. Kneis, and J. Kupke.
  On the approximation hardness of some generalizations of TSP.
  In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), number 4059 in Lecture Notes in Computer Science, pages 184-195. Springer, 2006.
  DOI, BibTeX.
• D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski.
  Centrality indices.
  In U. Brandes and T. Erlebach, editors, Network Analysis, volume 3418 of LNCS, pages 16-61. Springer, 2005.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  On the parameterized complexity of exact satisfiability problems.
  In J. Jedrzejowicz and A. Szepietowski, editors, Proceedings of the 30th Conference on Mathematical Foundations of Computer Science (MFCS), number 3618 in Lecture Notes in Computer Science, pages 568-579. Springer, 2005.
  Preprint, DOI, BibTeX.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  Algorithms based on the treewidth of sparse graphs.
  In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 3787 in Lecture Notes in Computer Science, pages 385-396. Springer, 2005.
  Preprint, DOI, BibTeX.
• S. Richter.
  Formalizing integration theory with an application to probabilistic algorithms.
  In Proc. of 17th TPHOLs, number 3223 in Lecture Notes in Computer Science, pages 271-286. Springer, 2004.
  Preprint.
• J. Gramm, R. Niedermeier, and P. Rossmanith.
  Exact solutions for closest string and related problems.
  In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC), number 2223 in Lecture Notes in Computer Science. Springer, 2001.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  On efficient fixed parameter algorithms for Weighted Vertex Cover.
  In Proceedings of the 11th International Symposium on Algorithms and Computation (ISAAC), number 1969 in Lecture Notes in Computer Science, Taipei, Taiwan, 2000. Springer.
• J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon.
  Efficient algorithms for model checking pushdown systems.
  In Proc. of CAV'2000, number 1855 in Lecture Notes in Computer Science, pages 232-247. Springer, 2000.
  Preprint.
• P. Rossmanith.
  Learning from random text.
  In O. Watanabe and T. Yokomori, editors, Proceedings of the 10th International Workshop on Algorithmic Learning Theory, number 1720 in Lecture Notes in Computer Science. Springer, December 1999.
• R. Niedermeier and P. Rossmanith.
  Upper bounds for Vertex Cover further improved.
  In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), number 1563 in Lecture Notes in Computer Science, pages 561-570. Springer, 1999.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  New upper bounds for MaxSat.
  In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP), number 1644 in Lecture Notes in Computer Science, pages 575-584. Springer, July 1999.
• P. Rossmanith and T. Zeugmann.
  Learning k-variable pattern languages efficiently stochastically finite on average from positive date.
  In V. Honavar and G. Slutzki, editors, Proceedings of the 4th International Colloquium on Grammatical Inference, number 1433 in Lecture Notes in Artificial Intelligence, pages 13-24, Ames, Iowa, jul 1998. Springer.
  Preprint.
• J. Esparza and P. Rossmanith.
  An automata approach to some problems on context-free grammars.
  In C. Freksa, M. Jantzen, and R. Valk, editors, Foundations of Computer Science: Potential--Theory--Cognition, number 1337 in Lecture Notes in Computer Science, pages 143-152. Springer, 1997.
  Preprint.
• T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.
  Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.
  In M. Li and A. Maruoka, editors, Proceedings of the 8th International Workshop on Algorithmic Learning Theory, number 1316 in Lecture Notes in Computer Science, pages 260-276. Springer, October 1997.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  PRAM's towards realistic parallelism: BRAM's.
  In H. Reichel, editor, Proceedings of the 10th Conference on Fundamentals of Computation Theory, number 965 in Lecture Notes in Computer Science, pages 363-373, Dresden, Federal Republic of Germany, August 1995. Springer.
  Preprint.
• M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.
  Optimal average case sorting on arrays.
  In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science (STACS), number 900 in Lecture Notes in Computer Science, pages 503-514. Springer, 1995.
  Preprint.
• K.-J. Lange and P. Rossmanith.
  Unambiguous polynomial hierarchies and exponential size.
  In Proceedings of the 9th IEEE Symposium on Structure in Complexity, pages 106-115, 1994.
  Preprint.
• M. Kunde, R. Niedermeier, and P. Rossmanith.
  Faster sorting and routing on grids with diagonals.
  In Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS), number 775 in Lecture Notes in Computer Science, pages 225-236. Springer, 1994.
  Preprint.
• C. Damm, M. Holzer, and P. Rossmanith.
  Expressing uniformity via oracles.
  In J. Dassow and A. Kelemenova, editors, Developments in Theoretical Computer Science: Proceedings of the International Meeting of Young Computer Scientists. Gordon and Breach Science Publishers, 1994.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  On the power of reading and writing simultaneously in parallel computations.
  In K. W. Ng, P. Raghavan, N. V. Balasubramanian, and F. Y. L. Chin, editors, Proceedings of the 4th International Symposium on Algorithms and Computation (ISAAC), number 762 in Lecture Notes in Computer Science, pages 240-249, Hong Kong, December 1993. Springer.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Extended locally definable acceptance types.
  In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science (STACS), number 665 in Lecture Notes in Computer Science, pages 473-483. Springer, 1993.
  Preprint.
• C. Damm, M. Holzer, K.-J. Lange, and P. Rossmanith.
  On the very low complexity of deterministic 0L languages.
  In G. Rozenberg and A. Salomaa, editors, Proceedings of Developments in Language Theory: At The Crossroads of Mathematics, Computer Science and Biology, Turku, Finland, July 1993. World Scientific.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Unambiguous simulations of auxiliary pushdown automata and circuits.
  In I. Simon, editor, Proceedings of the 1st Symposium on Latin American Theoretical Informatics (LATIN), number 583 in Lecture Notes in Computer Science, pages 387-400, São Paulo, Brazil, April 1992. Springer.
  Preprint.
• K.-J. Lange, P. Rossmanith, and W. Rytter.
  Parallel recognition and ranking of context-free languages.
  In I. Havel, editor, Proceedings of the 17th Conference on Mathematical Foundations of Computer Science (MFCS), number 629 in Lecture Notes in Computer Science, pages 24-36, Prague, Czechoslavakia, August 1992. Springer.
• K.-J. Lange and P. Rossmanith.
  The emptiness problem for intersections of regular languages.
  In I. Havel, editor, Proceedings of the 17th Conference on Mathematical Foundations of Computer Science (MFCS), number 629 in Lecture Notes in Computer Science, pages 346-354, Prague, Czechoslavakia, August 1992. Springer.
  Preprint.
• P. Rossmanith.
  The owner concept for PRAMs.
  In Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science (STACS), number 480 in Lecture Notes in Computer Science, pages 172-183, Hamburg, Federal Republic of Germany, February 1991. Springer.
  Preprint.
• I. Niepel and P. Rossmanith.
  Uniform circuits and exclusive read PRAMs.
  In S. Biswas and K. V. Nori, editors, Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), number 560 in Lecture Notes in Computer Science, pages 307-318, New Delhi, India, December 1991. Springer.
  Preprint.
• G. Buntrock, B. Jenner, K.-J. Lange, and P. Rossmanith.
  Unambiguity and fewness for logarithmic space.
  In L. Budach, editor, Proceedings of the 8th Conference on Fundamentals of Computation Theory, number 529 in Lecture Notes in Computer Science, pages 168-179, Gosen, Federal Republic of Germany, September 1991. Springer.
  Preprint.
• K.-J. Lange and P. Rossmanith.
  Characterizing unambiguous augmented pushdown automata by circuits.
  In B. Rovan, editor, Proceedings of the 15th Conference on Mathematical Foundations of Computer Science (MFCS), number 452 in Lecture Notes in Computer Science, pages 399-406, Banská Bystrica, Czechoslovakia, August 1990. Springer.
  Preprint.

Technical Reports

• J. Kneis, A. Langer, and P. Rossmanith.
  Derandomizing non-uniform color-coding I.
  Technical Report AIB-2009-07, RWTH Aachen University, March 2009.
  Download, BibTeX.
• J. Kneis and A. Langer.
  Satellites and mirrors for solving independent set on sparse graphs.
  Technical Report AIB-2009-08, RWTH Aachen University, April 2009.
  Download, BibTeX.
• J. Kneis, A. Langer, and P. Rossmanith.
  A new algorithm for finding trees with many leaves.
  Technical Report AIB-2008-15, Dept. of Computer Science, RWTH Aachen University, July 2008.
  Download, BibTeX.
• D. Mölle, S. Richter, and P. Rossmanith.
  A faster algorithm for the Steiner tree problem.
  Technical Report AIB-2005-04, Dept. of Computer Science, RWTH Aachen University, March 2005.
  Download, BibTeX.
• J. Kneis and P. Rossmanith.
  A new satisfiability algorithm with applications to Max-Cut.
  Technical Report AIB-2005-08, Dept. of Computer Science, RWTH Aachen University, April 2005. A short version to appear in Proc. of WG2005.
  Download, BibTeX.
• B. A. Madsen and P. Rossmanith.
  Maximum exact satisfiability: NP-completeness proofs and exact algorithms.
  Technical Report RS-04-19, BRICS, October 2004.
• J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
  Parameterized power domination complexity.
  Technical Report AIB-2004-09, Dept. of Computer Science, RWTH Aachen University, December 2004.
  Preprint, BibTeX.
• J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon.
  Efficient algorithms for model checking pushdown systems.
  Technical Report TUM-I0002, SFB-Bericht 342/1/00 A, Technische Universität München, Institut für Informatik, February 2000.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  A general method to speed up fixed-parameter-tractable algorithms.
  Technical Report TUM-I9913, Institut für Informatik, Technische Universität München,Fed. Rep. of Germany, June 1999. Revised version to appear in Information Processing Letters.
• R. Niedermeier and P. Rossmanith.
  An efficient fixed parameter algorithm for 3-Hitting Set.
  Technical Report WSI-99-18, WSI für Informatik, Universität Tübingen, Fed. Rep. of Germany, October 1999. Revised version accepted for publication in Journal of Discrete Algorithms.
• P. Rossmanith and T. Zeugmann.
  Learning k-variable pattern languages efficiently stochastic finite on average from positive data.
  DOI Technical Report DOI-TR-145, Department of Informatics, Kyushu University, January 1998.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Upper bounds for vertex cover further improved.
  Technical Report KAM-DIMATIA Series 98-411, Faculty of Mathematics and Physics, Charles University, Prague, November 1998.
• R. Niedermeier and P. Rossmanith.
  New upper bounds for MaxSat.
  Technical Report KAM-DIMATIA Series 98-401, Faculty of Mathematics and Physics, Charles University, Prague, July 1998. Extended abstract to appear at 26th International Colloquium on Automata, Languages, and Programming (ICALP'99), Prague, July 1999.
• R. Niedermeier and P. Rossmanith.
  Extended locally definable acceptance types.
  Technical Report WSI-96-25, Universität Tübingen, August 1996.
  Preprint.
• M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.
  Optimal deterministic sorting and routing on grids and tori with diagonals.
  Technical Report TUM-I9629, Technische Universität München, Institut für Informatik, July 1996.
  Preprint.
• T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.
  Efficient learning of one-variable pattern languages from positive examples.
  DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu University, December 1996.
  Preprint.
• C. Damm, M. Holzer, and P. Rossmanith.
  Expressing uniformity via oracles.
  Technical Report 95-01, Universität Trier, Fachbereich IV-Informatik und Mathematik, 54286 Trier, Fed. Rep. of Germany, January 1995.
  Preprint.
• M. Kunde, R. Niedermeier, and P. Rossmanith.
  Faster sorting and routing on grids with diagonals.
  Technical Report TUM-I9313, SFB-Bericht Nr. 342/5/93 A, Institut für Informatik, Technische Universität München, June 1993.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Optimal parallel algorithms for computing recursively defined functions.
  Technical Report TUM-I9218, SFB-Bericht Nr. 342/12/92 A, Technische Universität München, June 1992.
• P. Rossmanith.
  The owner concept for PRAMs.
  SFB-Bericht 342/15/90 A, I9028, Institut für Informatik, Technische Universität München, August 1990.
  Preprint.
• I. Niepel and P. Rossmanith.
  Uniform circuits and exclusive read PRAMs.
  SFB-Bericht 342/31/90 A, I9055, Institut für Informatik, Technische Universität München, December 1990.
  Preprint.
• R. Niedermeier and P. Rossmanith.
  Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits.
  SFB-Bericht 342/31/90 A, I9054, Institut für Informatik, Technische Universität München, December 1990.
• K.-J. Lange and P. Rossmanith.
  Two Results on Unambiguous Circuits.
  SFB-Bericht 342/3/90 A, I9006, Institut für Informatik, Technische Universität München, 1990.