50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Publications 2012


Proceedings

  • A. Bernstein, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störrle, D. Wagner::
    Ausgezeichnete Informatikdissertationen 2011.
    Volume D-12 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2012.

Journal articles

  • Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau:
    Smoothed Analysis of Left-To-Right Maxima with Applications.
    ACM Transactions on Algorithms, 8(3):Article No. 30, 2012.
    Go to website | Show abstract
  • Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan:
    Approximation Algorithms for Orienting Mixed Graphs.
    Theoretical Computer Science, 2012 (to appear).
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Theoretical Computer Science, 432:38–51, 2012.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33–47, 2012.
    Show PDF | Go to website | Show abstract
  • Maciej Liskiewicz, Martin R. Schuster:
    Improved Analysis of an Exact Algorithm for Cubic Graph TSP.
    CoRR, (abs/1207.4694)2012.
    Go to website
  • Johannes Textor, Maciej Liskiewicz:
    Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
    CoRR, (abs/1202.3764)2012.
    Go to website

Conference papers

  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
    In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space Complexity of Parameterized Problems.
    In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Volume 7535 of Lecture Notes in Computer Science, pp. 206-217. Springer, 2012.
    Go to website | Show abstract
  • Michael Elberfeld, Martin Grohe, Till Tantau:
    Where First-Order and Monadic Second-Order Logic Coincide.
    In Proceedings of the 27th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2012), pp. 265-274. IEEE Computer Society, 2012.
    Show PDF | Go to website | Show abstract

Technical reports

  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space Complexity of Parameterized Problems.
    Technical report , ECCC, 2012.
    Go to website | Show PDF | Show abstract

PhD theses

  • Michael Elberfeld:
    Space and Circuit Complexity of Monadic Second-Order Definable Problems on Tree-Decomposable Structures.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Till Tantau, Heribert Vollmer, Rolf Niedermeier.
    Show PDF | Show abstract

Masters theses

  • Yulia Bulygina:
    Sichere Zwei-Parteien Protokolle zur Berechnung von Entscheidungsbäumen.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Maciej Liskiewicz, Rüdiger Reischuk.
  • Sylvia Kiencke:
    Data-based Projection Access Order for SART.
    Universität zu Lübeck, Institut für Medizintechnik, 2012.
    Supervised by: Thorsten M. Buzug, Till Tantau.
  • Christian Pohlmann:
    DSL-based Runtime Verification for the JVM.
    Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
    Supervised by: Martin Leucker, Rüdiger Reischuk.
  • Martin Schuster:
    Exact Algorithms for Traveling Salesman Problem in Cubic Graphs.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Maciej Liskiewicz, Martin Leucker.
  • Christopher Strecker:
    Digital Camera Identification.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Rüdiger Reischuk, Maciej Liskiewicz.
  • Niels Thole:
    Dekomposition von Bäumen und Termin in AC0 und TC0.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Till Tantau, Maciej Liskiewicz.

Bachelors theses

  • Max Bannach:
    Berechnungskomplexitäten von Varianten des Subset-Sum-Problems.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Till Tantau, Hans-Martin Teichert.
    Show PDF | Show abstract
  • Moritz Bürger:
    Multimengen-Baumautomaten: Analyse und Implementierung.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Till Tantau, Martin Leucker.
  • Sören Grothkopp:
    Eine Multicommodity Push-Relabel-Algorithmus und Anwendung für parametrisierte Graphen.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Rüdiger Reischuk, Maciej Liskiewicz.
  • Philip Harms:
    Turn Costs in Energy-Optimal Route Planning for Electric Vehicles.
    Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
    Supervised by: Martin Leucker, Maciej Liskiewicz.
  • Ingmar Kaden:
    Lösungsstrategien und semiautomatische Generierung von Testdatensätzen bei ACM-ICPC-artigen Graphproblemen.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Maciej Liskiewicz, Till Tantau.
  • Christofer Krüger:
    Algorithmen und Datenstrukturen für Prioritätswarteschlangen auf partiellen Ordnungen.
    Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
    Supervised by: Martin Leucker, Maciej Liskiewicz.
  • Sarah Mäusle:
    Implementation and Comparison of Algorithms for Constructing and Visualizing Phylogenetic Trees.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Till Tantau, Hans-Martin Teichert.
    Show PDF | Show abstract
  • Malte Schmitz:
    Transformation von regulärer Linearzeit-Temporallogik zu Paritätsautomaten.
    Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
    Supervised by: Martin Leucker, Till Tantau.
  • Benjamin Winter:
    Steganographie in Binärbildern.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Maciej Liskiewicz, Rüdiger Reischuk.
  • Fabian Winter:
    Synchronisierungsmethoden zur Huffmankodierung.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
    Supervised by: Maciej Liskiewicz, Andreas Schrader.