Veröffentlichungen

Diese Seite enthält eine Liste meiner Veröffentlichungen mit Verweisen zu herunterladbaren Versionen.

2019

  • Yijia Chen, Michael Elberfeld, Moritz Müller:
    The parameterized space complexity of model-checking bounded variable first-order logic
    Log. Methods Comput. Sci., 15 (3), 2019.
    Webseite

2018

  • Marco Bender, Sebastian Berckey, Michael Elberfeld, Jörg Herbers:
    Real-World Staff Rostering via Branch-and-Price in a Declarative Framework
    In Operations Research Proceedings 2018, Selected Papers of the Annual International Conference of the German Operations Research Society (GOR).pp. 445-451, 2018
    Webseite

2017

  • Kord Eickmeyer, Michael Elberfeld, Frederik Harwath:
    Succinctness of Order-Invariant Logics on Depth-Bounded Structures
    ACM Trans. Comput. Log., 18 (3), 2017.
    Webseite
  • Michael Elberfeld, Pascal Schweitzer:
    Canonizing Graphs of Bounded Tree Width in Logspace
    ACM Trans. Comput. Theory, 9 (3), 2017.
    Webseite

2016

  • Michael Elberfeld:
    Context-Free Graph Properties via Definable Decompositions.
    In Proceedings of the 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Volume 62 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 17:1-17:16. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016.
    Webseite
  • Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe:
    Order Invariance on Decomposable Structures.
    In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016). pp. 397-406. IEEE Computer Society, 2016.
    Webseite | arXiv Preprint
  • Michael Elberfeld, Pascal Schweitzer:
    Canonizing Graphs of Bounded Tree Width in Logspace.
    In Proceedings of the 33th International Symposium on Theoretical Aspects of Computer Science (STACS 2016), Volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 32:1-32:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016.
    Webseite | arXiv Preprint
  • Michael Elberfeld:
    Variants of Courcelle's Theorem for Complexity Classes Inside P.
    ACM SIGLOG News, 3(1):23-32, 2016.
    Webseite
  • Michael Elberfeld, Martin Grohe, Till Tantau:
    Where First-Order and Monadic Second-Order Logic Coincide.
    ACM Transactions on Computational Logic, 17(4), 2016.
    Webseite

2015

  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
    Algorithmica, 71(3), 2015.
    Webseite

2014

  • Christoph Berkholz, Michael Elberfeld:
    Parameterized Complexity of Fixed-Variable Logics.
    In Proceedings of the 34th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014). pp. 109-120. Dagstuhl, 2014.
    Webseite
  • Kord Eickmeyer, Michael Elberfeld, Frederik Harwath:
    Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures.
    In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), pp. 256-266. Springer, 2014.
    Webseite | arXiv Preprint
  • Michael Elberfeld, Ken-ichi Kawarabayashi:
    Embedding and Canonizing Graphs of Bounded Genus in Logspace.
    In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC 2014), pp. 383-392. ACM, 2014.
    Webseite

2013

  • Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan:
    Approximation Algorithms for Orienting Mixed Graphs.
    Theoretical Computer Science, 483:96-103, 2013.
    Webseite | PDF Preprint

2012

  • 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 (Dissertation).
    PDF
  • Michael Elberfeld:
    Platz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen
    In Ausgezeichnete Informatikdissertationen 2012, pp. 71-80. LNI, Gesellschaft für Informatik, 2012.
    Webseite
  • 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.
    Webseite | ECCC Preprint
  • 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.
    Webseite | PDF Preprint
  • 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.
    Webseite | ECCC Preprint
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33-47, 2012.
    Webseite | PDF Preprint
  • 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.
    Webseite | arXiv Preprint

2011

  • Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan:
    Approximation Algorithms for Orienting Mixed Graphs.
    In Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), Volume 6661 of Lecture Notes in Computer Science, pp. 416-428. Springer, 2011.
    Webseite
  • Michael Elberfeld, Johannes Textor:
    Negative Selection Algorithms on Strings with Efficient Training and Linear-Time Classification.
    Theoretical Computer Science, 412(6):534-542, 2011.
    Webseite | PDF Preprint
  • Michael Elberfeld, Vineet Bafna, Iftah Gamzu, Alexander Medvedovsky, Danny Segev, Dana Silverbush, Uri Zwick, Roded Sharan:
    On the Approximability of Reachability-Preserving Network Orientations.
    Internet Mathematics, 4(7):209-232, 2011.
    Webseite | PDF Preprint
  • Dana Silverbush, Michael Elberfeld, Roded Sharan:
    Optimally Orienting Physical Networks.
    In Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011), Volume 6577 of Lecture Notes in Computer Science, pp. 424-436. Springer, 2011.
    Webseite | PDF Preprint
  • Dana Silverbush, Michael Elberfeld, Roded Sharan:
    Optimally Orienting Physical Networks.
    Journal of Computational Biology, 18(11):1437-1448, 2011.
    Webseite

2010

  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Logspace Versions of the Theorems of Bodlaender and Courcelle.
    In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 143-152. IEEE Computer Society, 2010.
    Webseite | ECCC Preprint
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Volume 6129 of Lecture Notes in Computer Science, pp. 177-189. Springer, 2010.
    Webseite

2009

  • Michael Elberfeld, Johannes Textor:
    Efficient Algorithms for String-Based Negative Selection.
    In Proceedings of the 8th International Conference on Artificial Immune Systems (ICARIS 2009), Volume 5666 of Lecture Notes in Computer Science, pp. 109-121. Springer, 2009.
    Webseite | PDF Preprint
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 201-210. Springer, 2009.
    Webseite | PDF Preprint
  • Michael Elberfeld:
    Perfect Phylogeny Haplotyping is Complete for Logspace.
    Technical report abs/0905.0602 [cs.CC], Computing Research Repository (CoRR), 2009.
    Webseite

2008

  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Volume 5162 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2008.
    Webseite | PDF Preprint

2007

  • Michael Elberfeld:
    Komplexität von Haplotypisierung mittels perfekten Phylogenien und kleinsten Haplotypmengen.
    Universität zu Lübeck, Institut für Theoretische Informatik, 2007 (Diploma Thesis, in German).
    PDF