Research @ Chair of Theoretical Computer Science

Our research covers many aspects of Theoretical Computer Science, focussing on: efficient graph algorithms, parameterized algorithms and complexity, approximation algorithms and complexity, formal languages and grammar induction.

A good first impression is obtained by browsing through our publications.

In the following, you can find a list of papers of members of our research group of this year. Regarding previous years, we refer to the menu to the left. For complete lists of publications, we refer to the homepages of each of the group members.

Publications

Accepted for publication in journals:

  • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman. On the computational completeness of matrix simple semi-conditional grammars. Information and Computation.

  • Henning Fernau, Lakshmanan Kuppusamy, Rufus Oladele, Indhumathi Raman. Improved Descriptional Complexity Results on Generalized Forbidding Grammars. Discrete Applied Mathematics.

  • Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides. Combinatorial Properties and Recognition of Unit Square Visibility Graphs. Discrete & Computational Geometry.

  • Martin Vu, Henning Fernau. Insertion-Deletion Systems With Substitutions I. Computability.
  • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman. On the generative capacity of matrix insertion-deletion systems of small sum-norm. Natural Computing.