jens gramm
(publications)
Journal Articles
J. Alber, J. Gramm and R. Niedermeier. Faster exact algorithms for hard problems: a parameterized point of view. Discrete Mathematics 229:3-27, 2001, Elsevier.

J. Gramm, E.A. Hirsch, R. Niedermeier and P. Rossmanith. Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. Discrete Applied Mathematics 130(2):139--155, 2003.

J. Gramm and R. Niedermeier. A fixed-parameter algorithm for Minimum Quartet Inconsistency. Journal of Computer and System Sciences 67(4):723--741, 2003.

J. Gramm, R. Niedermeier, and P. Rossmanith. Fixed-parameter algorithms for Closest String and related problems. Algorithmica 37(1):25--42, 2003, Springer.

J. Alber, J. Gramm, J. Guo and R. Niedermeier. Computing the similarity of two sequences with nested arc annotations. Theoretical Computer Science 312(2-3):337--358. 2004.

J. Gramm, J. Guo, F. Hüffner and R. Niedermeier. Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems. Algorithmica, 39(4):321--347, 2004.

J. Gramm, J. Guo, F. Hüffner and R. Niedermeier. Graph-modeled data clustering: fixed-parameter algorithms for clique generation. Accepted for publication in Theory of Computing Systems. To appear.

J. Gramm, J. Guo and R. Niedermeier. Parameterized intractability of Distinguishing Substring Selection. Accepted for publication in Theory of Computing Systems. To appear.

Michael R. Fellows, J. Gramm, and R. Niedermeier. On the parameterized intractability of motif search problems. Accepted for publication in Combinatorica. To appear.

Conference Articles J. Gramm and R. Niedermeier. Faster exact solutions for Max2Sat. In G. Bongiovanni, G. Gambosi, R. Petreschi (Eds.): Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC 2000), Lecture Notes in Computer Science, volume number 1767, 174-186, Rome, Italy, March 2000, Springer. (.ps.gz)

J. Gramm and R. Niedermeier. Minimum Quartet Inconsistency is fixed parameter tractable. In A. Amir, G.M. Landau (Eds.): Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), Lecture Notes in Computer Science, volume number 2089, 241-256, Jerusalem, Israel, July 2001, Springer. (.ps.gz)

J. Gramm, R. Niedermeier and Peter Rossmanith. Exact solutions for Closest String and related problems. In P. Eades, T. Takaoka (Eds.): Proceedings of the 12th Annual Symposium on Algorithms and Computation (ISAAC 2001), Lecture Notes in Computer Science, volume number 2223, 441-453, Christchurch, New Zealand, December 2001, Springer. (.ps.gz).

M.R. Fellows, J. Gramm and R. Niedermeier. On the parameterized intractability of Closest Substring and related problems. In H. Alt, A. Ferreira (Eds.): Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Lecture Notes in Computer Science, volume number 2285, 262-273, Antibes/Juan-Les-Pins, France, March 2002, Springer. (.ps.gz).

J. Alber, J. Gramm, J. Guo and R. Niedermeier. Towards optimally solving the Longest Common Subsequence problem for sequences with nested arc annotations in linear time. In A. Apostolico, M. Takeda (Eds.): Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), Lecture Notes in Computer Science, volume number 2373, 99-114, Fukuoka, Japan, July 2002, Springer. (.ps.gz)

J. Gramm and R. Niedermeier. Breakpoint medians and breakpoint phylogenies - a fixed-parameter approach. In T. Lengauer, H.-P. Lenhof (Eds.): Proceedings of the 1st European Conference on Computational Biology (ECCB 2002), Bioinformatics 18 (Supplement 2):S128-S139. Oxford University Press. (.ps.gz)

J. Gramm, J. Guo and R. Niedermeier. Pattern matching for arc-annotated sequences. In M. Agrawal, A. Seth (Eds.): Proceedings of the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FST TCS 2002), Lecture Notes in Computer Science, volume number 2556, 182-193, Kanpur, India, December 2002, Springer. (.ps.gz)

J. Gramm, J. Guo, F. Hüffner and R. Niedermeier. Graph-modeled data clustering: fixed-parameter algorithms for clique generation. Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC 2003), Lecture Notes in Computer Science, volume number 2653, 108-119, Rome, Italy, May 2003, Springer. (.ps.gz)

J. Gramm, J. Guo and R. Niedermeier. On exact and approximation algorithms for distinguishing substring selection. Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Lecture Notes in Computer Science, volume number 2751, pages 195--209, Malmö, Sweden, August 2003, Springer. (.ps.gz)

J. Gramm, J. Guo, F. Hüffner and R. Niedermeier. Automated generation of search tree algorithms for graph modification problems. Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, volume number 2832, pages 642--653, Budapest, Hungary, September 2003. (.ps.gz)

S. Wernicke, J. Alber, J. Gramm, J. Guo, and R. Niedermeier. Avoiding Forbidden Submatrices by Row Deletions. In Proceedings of the 30th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2004), Lecture Notes in Computer Science, volume number 2832, pages 349--360, Springer, 2004.

J. Gramm, T. Nierhoff, T. Tantau, and R. Sharan. On the Complexity of Haplotyping Via Perfect Phylogeny. Presented at the Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, February 20-21, Pittsburgh, USA. Proceedings to appear in LNBI, Springer, 2004.

J. Gramm. A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns. Accepted for the 4th International Workshop on Algorithms in Bioinformatics (WABI 2004), Bergen, Norway, September 2004. Proceedings to appear in LNBI, Springer.

J. Gramm, T. Nierhoff, and T. Tantau. Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable. Accepted for the First International Workshop on Parametrized and Exact Computation (IWPEC 2004), Bergen, Norway, September 2004. Proceedings to appear in LNCS, Springer.
Reports J. Gramm, E.A. Hirsch, R. Niedermeier and P. Rossmanith. New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. ECCC Technical Report TR00-037, Trier, Fed. Rep. of Germany. Presented at SAT 2000, Renesse, The Netherlands, May 2000.

J. Gramm and R. Niedermeier. Minimum Quartet Inconsistency is fixed parameter tractable. Technical Report WSI-2001-3, Wilhelm-Schickard Institut für Informatik, Universität Tübingen, 2001 (29 pages, postscript , gzipped ).

M. R. Fellows, J. Gramm and R. Niedermeier. Parameterized intractability of motif search problems.. Technical Report WSI-2001-2, Wilhelm-Schickard Institut für Informatik, Universität Tübingen, May 2002.
Posters
J. Gramm and R. Niedermeier. Evaluating an algorithm for parameterized Minimum Quartet Inconsistency. Presented at RECOMB 2001 (Fifth Annual International Conference on Computational Molecular Biology), Montreal, Canada, April 2001. Abstract appeared in In N. El-Mabrouk, T. Lengauer, and D. Sankoff (eds.) Currents in Computational Molecular Biology 2001. Les Publications CRM; Montreal, p. 195/196.

J. Gramm, F. Hüffner and R. Niedermeier. Closest strings, primer design, and motif search. Presented at RECOMB 2002 (Sixth Annual International Conference on Computational Molecular Biology), Washington DC, USA, April 2002. In L. Florea, B. Walenz, S. Hannenhalli (eds.) Currents in Computational Molecular Biology 2002, pp. 74/5.
Theses
J. Gramm. Exact algorithms for Max2Sat and their applications. Diplomarbeit, Universität Tübingen, October 1999 (92 pages, postscript , gzipped ).
Applet demonstrating one of our Max2Sat algorithms.

J. Gramm. Fixed-Parameter Algorithms for the Consensus Analysis of Genomic Sequences. Dissertation, Universität Tübingen, April 2003 (209 pages, postscript , gzipped ).