You can find here our publications in journals, conference proceedings,
and our technical reports.
Articles in Journals

A new algorithm for finding trees with many leaves.Algorithmica, 61(4):882897, 2011.

Courcelle's Theorem  a gametheoretic approach.Discrete Optimization, 8(4):568594, 2011.

A property tester for treelikeness of quartet topologies.Theory Comput. Syst., 49(3):576587, 2011.

New fixedparameter algorithms for the minimum quartet inconsistency problem.Theory Comput. Syst., 47(2):342367, 2010.

A bound on the pathwidth of sparse graphs with applications to exact algorithms.SIAM Journal on Discrete Mathematics, 23(1):407427, 2009.

A practical approach to Courcelle's Theorem.Electronic Notes in Theoretical Computer Science, 251:6581, 2009.

Randomized divideandconquer: Improved path, matching, and packing algorithms.SIAM Journal on Computing, 38(6):25262547, 2009.

Approximation hardness of deadlinetsp reoptimization.Theor. Comput. Sci., 410(2123):22412249, 2009.

Reoptimization of steiner trees: Changing the terminal set.Theoretical Computer Science, 410(36):34283435, 2009.

Enumerate and expand: Improved algorithms for connected vertex cover and tree cover.Theory of Computing Systems, 43(2):234253, 2008.

Dynamic programming for minimum Steiner trees.Theory of Computing Systems, 41(3):493500, 2007.

The parameterized approximability of TSP with deadlines.Theory of Computing Systems, 41(3):431444, 2007.

On the approximability of TSP on local modifications of optimally solved instances.Algorithmic Operations Research, 2(2):8393, 2007.

Parameterized power domination complexity.Information Processing Letters, 98(4):145149, 2006.

On efficient fixed parameter algorithms for Weighted Vertex Cover.Journal of Algorithms, 47:6377, 2003.

An efficient fixed parameter algorithm for 3hitting set.Journal of Discrete Algorithms, 1:89102, 2003.

Fixedparameter algorithms for closest string and related problems.Algorithmica, 37(1):2542, 2003.

New worstcase upper bounds for MAX2SAT with application to MAXCUT.Discrete Applied Mathematics, 130(2):139155, 2003.

Stochastic finite learning of the pattern languages.Machine Learning, 44(1/2):6791, 2001.

Learning onevariable pattern languages very efficiently on average, in parallel, and by asking queries.Theoretical Computer Science, 261:119156, 2001.

New upper bounds for maximum satisfiability.Journal of Algorithms, 36:6388, 2000.

A general method to speed up fixedparametertractable algorithms.Information Processing Letters, 73:125129, 2000.

A uniform framework for problems on contextfree grammars.EATCS Bulletin, 72:169177, October 2000.

An efficient automata approach to some problems on contextfree grammars.Information Processing Letters, 74(56):221227, 2000.

Optimal deterministic sorting and routing on grids and tori with diagonals.Algorithmica, (25):438458, 1999.

Unambiguous computations and locally definable acceptance types.Theoretical Computer Science, (194):137161, 1998.

Expressing uniformity via oracles.Theory of Computing Systems, 30:355366, 1997.

A simpler grammar for Fibonacci numbers.The Fibonacci Quarterly, 34(5):465466, November 1996.

Unambiguous auxiliary pushdown automata and semiunbounded fanin circuits.Information and Computation, 118(2):227245, May 1995.

On optimal OROWPRAM algorithms for computing recursively defined functions.Parallel Processing Letters, 5(2):299309, June 1995.

Observations on time parallel recognition ,of unambiguous contextfree languages.Information Processing Letters, 44:267272, 1992.
Contributions in Refereed Conference Proceedings

Evaluation of an MSOsolver.In Proceedings of ALENEX'12, 2012. To appear.

A parameterized route to exact puzzles: Breaking the 2^{n}barrier for irredundance.In T. Calamoneri and J. Díaz, editors, Proceedings of the 7th Italian Conference on Algorithms and Complexity, number 6078 in Lecture Notes in Computer Science, pages 311322. Springer, 2010.

Dynamic programming on tree decompositions using generalised fast subset convolution.In ESA, volume 5757 of Lecture Notes in Computer Science, pages 566577. Springer, 2009.

NISAN: Network information service for anonymization networks.In Proceedings of CCS 2009, 2009. to appear.

A finegrained analysis of a simple independent set algorithm.In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 287298, 2009.

Breaking anonymity by learning a unique minimum hitting set.In Proceedings of the 4th International Computer Science Symposium in Russia (CSR), number 5675 in Lecture Notes in Computer Science. Springer, 2009.

On digraph width measures in parameterized algorithmics.In Proc. of IWPEC'2009, number 5917 in Lecture Notes in Computer Science, pages 185197. Springer, 2009.

An exact algorithm for the maximum leaf spanning tree problem.In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), number 5917 in Lecture Notes in Computer Science, pages 161172. Springer, 2009.

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 270281. Springer, 2008.

Improved upper bounds for partial vertex cover.In Proceedings of the 34th International Workshop on GraphTheoretic Concepts in Computer Science (WG), number 5344 in Lecture Notes in Computer Science, pages 240251. Springer, 2008.

A practical approach to Courcelle's Theorem.In Proceedings of the 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS), pages 99106. Z. Novotný, 2008.

New fixedparameter 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 6677. Springer, 2008.

Partial vs. complete domination: tdominating 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 367376. Springer, 2007.

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 561570. Springer, 2006.

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 265273. Springer, 2006.

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 270280. Springer, 2006.

Intuitive algorithms and tvertex cover.In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), number 4288 in Lecture Notes in Computer Science, pages 598607. Springer, 2006.

Divideandcolor.In Proceedings of the 32nd International Workshop on GraphTheoretic Concepts in Computer Science (WG), number 4271 in Lecture Notes in Computer Science, pages 5867. Springer, 2006.

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 184195. Springer, 2006.

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 251270. Springer, 2006.

Centrality indices.In U. Brandes and T. Erlebach, editors, Network Analysis, volume 3418 of LNCS, pages 1661. Springer, 2005.

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 568579. Springer, 2005.

Algorithms based on the treewidth of sparse graphs.In Proceedings of the 31st International Workshop on GraphTheoretic Concepts in Computer Science (WG), number 3787 in Lecture Notes in Computer Science, pages 385396. Springer, 2005.

Formalizing integration theory with an application to probabilistic algorithms.In Proc. of 17th TPHOLs, number 3223 in Lecture Notes in Computer Science, pages 271286. Springer, 2004.

Generic programming for scientific computing in C++, Java, and C#.In Proceedings of the 5th International Workshop on Advanced Parallel Programming Technologies, number 2834 in Lecture Notes in Computer Science, pages 301310. Springer, 2003.

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.

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.

Efficient algorithms for model checking pushdown systems.In Proc. of CAV'2000, number 1855 in Lecture Notes in Computer Science, pages 232247. Springer, 2000.

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.

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 561570. Springer, 1999.

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 575584. Springer, July 1999.

Learning kvariable 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 1324, Ames, Iowa, jul 1998. Springer.

An automata approach to some problems on contextfree grammars.In C. Freksa, M. Jantzen, and R. Valk, editors, Foundations of Computer Science: PotentialTheoryCognition, number 1337 in Lecture Notes in Computer Science, pages 143152. Springer, 1997.

Learning onevariable 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 260276. Springer, October 1997.

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 363373, Dresden, Federal Republic of Germany, August 1995. Springer.

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 503514. Springer, 1995.

Unambiguous polynomial hierarchies and exponential size.In Proceedings of the 9th IEEE Symposium on Structure in Complexity, pages 106115, 1994.

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 225236. Springer, 1994.

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.

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 240249, Hong Kong, December 1993. Springer.

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 473483. Springer, 1993.

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.

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 387400, São Paulo, Brazil, April 1992. Springer.

Parallel recognition and ranking of contextfree 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 2436, Prague, Czechoslavakia, August 1992. Springer.

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 346354, Prague, Czechoslavakia, August 1992. Springer.

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 172183, Hamburg, Federal Republic of Germany, February 1991. Springer.

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 307318, New Delhi, India, December 1991. Springer.

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 168179, Gosen, Federal Republic of Germany, September 1991. Springer.

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 399406, Banská Bystrica, Czechoslovakia, August 1990. Springer.
Technical Reports

Derandomizing nonuniform colorcoding I.Technical Report AIB200907, RWTH Aachen University, March 2009.

Satellites and mirrors for solving independent set on sparse graphs.Technical Report AIB200908, RWTH Aachen University, April 2009.

Breaking the 2^{n}barrier for irredundance: A parameterized route to solving exact puzzles.Technical Report abs/0909.4224, CoRR, 2009.

A new algorithm for finding trees with many leaves.Technical Report AIB200815, Dept. of Computer Science, RWTH Aachen University, July 2008.

Divideandcolor.Technical Report AIB200606, RWTH Aachen University, May 2006.

A faster algorithm for the Steiner tree problem.Technical Report AIB200504, Dept. of Computer Science, RWTH Aachen University, March 2005.

A new satisfiability algorithm with applications to MaxCut.Technical Report AIB200508, Dept. of Computer Science, RWTH Aachen University, April 2005. A short version to appear in Proc. of WG2005.

Maximum exact satisfiability: NPcompleteness proofs and exact algorithms.Technical Report RS0419, BRICS, October 2004.

Parameterized power domination complexity.Technical Report AIB200409, Dept. of Computer Science, RWTH Aachen University, December 2004.

Efficient algorithms for model checking pushdown systems.Technical Report TUMI0002, SFBBericht 342/1/00 A, Technische Universität München, Institut für Informatik, February 2000.

A general method to speed up fixedparametertractable algorithms.Technical Report TUMI9913, Institut für Informatik, Technische Universität München,Fed. Rep. of Germany, June 1999. Revised version to appear in Information Processing Letters.

An efficient fixed parameter algorithm for 3Hitting Set.Technical Report WSI9918, WSI für Informatik, Universität Tübingen, Fed. Rep. of Germany, October 1999. Revised version accepted for publication in Journal of Discrete Algorithms.

Learning kvariable pattern languages efficiently stochastic finite on average from positive data.DOI Technical Report DOITR145, Department of Informatics, Kyushu University, January 1998.

Upper bounds for vertex cover further improved.Technical Report KAMDIMATIA Series 98411, Faculty of Mathematics and Physics, Charles University, Prague, November 1998.

New upper bounds for MaxSat.Technical Report KAMDIMATIA Series 98401, 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.

Extended locally definable acceptance types.Technical Report WSI9625, Universität Tübingen, August 1996.

Optimal deterministic sorting and routing on grids and tori with diagonals.Technical Report TUMI9629, Technische Universität München, Institut für Informatik, July 1996.

Efficient learning of onevariable pattern languages from positive examples.DOI Technical Report DOITR128, Department of Informatics, Kyushu University, December 1996.

Expressing uniformity via oracles.Technical Report 9501, Universität Trier, Fachbereich IVInformatik und Mathematik, 54286 Trier, Fed. Rep. of Germany, January 1995.

Faster sorting and routing on grids with diagonals.Technical Report TUMI9313, SFBBericht Nr. 342/5/93 A, Institut für Informatik, Technische Universität München, June 1993.

Optimal parallel algorithms for computing recursively defined functions.Technical Report TUMI9218, SFBBericht Nr. 342/12/92 A, Technische Universität München, June 1992.

The owner concept for PRAMs.SFBBericht 342/15/90 A, I9028, Institut für Informatik, Technische Universität München, August 1990.

Uniform circuits and exclusive read PRAMs.SFBBericht 342/31/90 A, I9055, Institut für Informatik, Technische Universität München, December 1990.

Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits.SFBBericht 342/31/90 A, I9054, Institut für Informatik, Technische Universität München, December 1990.

Two Results on Unambiguous Circuits.SFBBericht 342/3/90 A, I9006, Institut für Informatik, Technische Universität München, 1990.