Editorium

• A. Bernstein, W. Effelsberg, S. Hölldoble, H.-P. Lenhof, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, N. Schweikardt, M. Spiliopoulou, H. Störrle, S. Süsstrunk:
  Ausgezeichnete Informatikdissertationen 2012.
  Band 13 von Lecture Notes in Informatics, Dissertationen, GI, 2013.

Zeitschriftenartikel

• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-box steganography.
  Theoretical Computer Science, (505):27-41, 2013.
  Website anzeigen
• Till Tantau:
  Graph Drawing in TikZ.
  Journal of Graph Algorithms and Applications, 17(4):495-513, 2013.
  PDF anzeigen | Zusammenfassung anzeigen
  
  At the heart of every good graph drawing algorithm lies an efficient procedure for assigning canvas positions to a graph's nodes and the bend points of its edges. However, every real-world implementation of such an algorithm must address numerous problems that have little to do with the actual algorithm, like handling input and output for-mats, formatting node texts, and styling nodes and edges. We present a new framework, implemented in the Lua programming language and integrated into the TikZ graphics description language, that aims at sim-plifying the implementation of graph drawing algorithms. Implementers using the framework can focus on the core algorithmic ideas and will au-tomatically profit from the framework's pre- and post-processing steps as well as from the extensive capabilities of the TikZ graphics language and the TeX typesetting engine. Algorithms already implemented using the framework include the Reingold-Tilford tree drawing algorithm, a mod-ular version of Sugiyama's layered algorithm, and several force-based multilevel algorithms.

Konferenzbeiträge

• Maciej Liskiewicz, Martin R. Schuster:
  A new upper bound for the traveling salesman problem in cubic graphs.
  In 12th Cologne-Twente Workshop on Graphs and Combinatorial, Optimization, Enschede, Netherlands, May 21-23, 2013, Band WP 13-01 von CTIT Workshop Proceedings, S. 159-162. , 2013.
• Christoph Stockhusen, Till Tantau:
  Completeness Results for Parameterized Space Classes.
  In 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Lecture Notes in Computer Science, Springer, 2013 (noch nicht erschienen).
  Zusammenfassung anzeigen
  
  The parameterized complexity of a problem is generally considered ``settled'' once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized \emph{space} complexity have recently been obtained that rule out completeness results for parameterized \emph{time} classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a ``union operation'' that translates between problems complete for classical complexity classes and for W-classes.
• Till Tantau:
  Graph Drawing in TikZ.
  In Proceedings of Graph Drawing 2012, Band 7704 von Lecture Notes in Computer Science, S. 517-528. Springer, 2013.
  Zusammenfassung anzeigen
  
  At the heart of every good graph drawing algorithm lies an efficient procedure for assigning canvas positions to a graph's nodes and the bend points of its edges. However, every real-world implementation of such an algorithm must address numerous problems that have little to do with the actual algorithm, like handling input and output for-mats, formatting node texts, and styling nodes and edges. We present a new framework, implemented in the Lua programming language and integrated into the TikZ graphics description language, that aims at sim-plifying the implementation of graph drawing algorithms. Implementers using the framework can focus on the core algorithmic ideas and will au-tomatically profit from the framework's pre- and post-processing steps as well as from the extensive capabilities of the TikZ graphics language and the TeX typesetting engine. Algorithms already implemented using the framework include the Reingold-Tilford tree drawing algorithm, a mod-ular version of Sugiyama's layered algorithm, and several force-based multilevel algorithms.

Technische Berichte

• Christoph Stockhusen, Till Tantau:
  Completeness Results for Parameterized Space Classes.
  Technischer Bericht arxiv:1308.2892, ArXiv, 2013.
  Website anzeigen | Zusammenfassung anzeigen
  
  The parameterized complexity of a problem is considered "settled" once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a "union operation" that translates between problems complete for classical complexity classes and for W-classes.

Master- und Diplomarbeiten

• M. E.:
  Algorithmisches Lernen von Verteilungen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Rüdiger Reischuk, Karsten Keller.
• S. F.:
  Das fehlertolerante Shortest-Common-Superstring-Problem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Rüdiger Reischuk, Till Tantau.
• N. F.:
  Reoptimization of the Travelling Salesperson Problem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Rüdiger Reischuk, Till Tantau.
• C. W.:
  Runtime Verification for Mazurkiewicz Traces.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2013.
  Gutachter: Martin Leucker, Rüdiger Reischuk.

Bachelor- und Studienarbeiten

• R. B.:
  Implementierung und experimentelle Untersuchung des exakten TSP-Algorithmus von Eppstein für kubische Graphen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Till Tantau.
• K. D.:
  Fast Algorithms for Immune Response Simulations in Models with r-Contiguous-Based Affinity Measures.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Amir Madany Mamlouk.
• A. I.:
  Mehrdimensionale Histogram Equalization: Modellierung und komplexitätstheoretische Analyse.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Martin Leucker.
• T. P.:
  Fußballprognose mit Hilfe der Poisson Verteilung und Bayesschen Netzwerken.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Andreas Schrader.
• M. S.:
  Algorithm for anomaly detection using string-based Negative Selection.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Andreas Schrader.
• T. S.:
  Lokale Suchstrategien für Erfüllbarkeitsprobleme.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Rüdiger Reischuk, Maciej Liskiewicz.
• M. S.:
  Stabilität des natürlichen Codes unter Shiftmutation.
  Universität zu Lübeck, Institut für Neuro- und Bioinformatik, 2013.
  Gutachter: Amir Madany Mamlouk, Till Tantau.
• F. T.:
  Eine Analyse der Konzepte von Sicherheit und Detektierbarkeit von steganographischen Verfahren.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz, Rüdiger Reischuk.
• N. V.:
  Experimentelle Analyse des Ensemble-Classifiers für die Steganalyse von digitalen Bildern.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2013.
  Gutachter: Maciej Liskiewicz.