50 Jahre Uni Lübeck

Prof. Dr. Till Tantau

Veröffentlichungen


Konferenzbeiträge

  • Klaus Didrich, Wolfgang Grieskamp, Florian Schintke, Till Tantau, Baltasar Trancón-y-Widemann:
    Reflections in Opal - Meta Information in a Functional Programming Language.
    In Proceedings of the 11th International Workshop on Implementation of Functional Languages, Lochem, The Netherlands, September 1999, (IFL'99), Selected Papers, Band 1868 von Lecture Notes in Computer Science, S. 146--164. Springer, 2000.
    Zusammenfassung anzeigen
  • Arfst Nickelsen, Till Tantau:
    Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.
    In Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001), Band 2138 von Lecture Notes in Computer Science, S. 299-310. Springer, 2001.
    Website anzeigen | Zusammenfassung anzeigen
  • Arfst Nickelsen, Till Tantau:
    On Reachability in Graphs with Bounded Independence Number.
    In Proceedings of the Eighth Annual International Computing and Combinatorics Conference (COCOON 2002), Band 2387 von Lecture Notes in Computer Science, S. 554--563. Springer, 2002.
    Zusammenfassung anzeigen
  • Till Tantau:
    Comparing Verboseness for Finite Automata and Turing Machines.
    In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Band 2285 von Lecture Notes in Computer Science, S. 465-476. Springer, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Towards a Cardinality Theorem for Finite Automata.
    In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Band 2420 von Lecture Notes in Computer Science, S. 625-636. Springer, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Computation with Absolutely No Space Overhead.
    In Proceedings of the Seventh International Conference on Developments in Language Theory (DLT 2003), Band 2710 von Lecture Notes in Computer Science, S. 325-336. Springer, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Band 2751 von Lecture Notes in Computer Science, S. 400-411. Springer, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of Haplotyping via Perfect Phylogeny.
    In Proceedings of Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, S. 35-46. , 2004.
    Zusammenfassung anzeigen
  • Jens Gramm, Till Nierhoff, Till Tantau:
    Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable.
    In Proceedings of the 2004 International Workshop on Parameterized and Exact Computation, Band 3162 von Lecture Notes in Computer Science, S. 174-186. Springer, 2004.
    Zusammenfassung anzeigen
  • Till Tantau:
    Über strukturelle Gemeinsamkeiten der Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
    In Ausgezeichnete Informatikdissertationen 2003, Lecture Notes in Informatics, S. 189-198. Springer, 2004.
    Zusammenfassung anzeigen
  • Richard Karp, Till Nierhoff, Till Tantau:
    Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
    In Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Band 19 von Electronic Notes in Discrete Mathematics, S. 225-231. Springer, 2005.
    Zusammenfassung anzeigen
  • Till Tantau:
    Logspace Optimization Problems and Their Approximability Properties.
    In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Band 3623 von Lecture Notes in Computer Science, S. 92-103. Springer, 2005.
    Zusammenfassung anzeigen
  • Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
    In Proceedings of Workshop on Algorithms in Bioinformatics (WABI), Band 4175 von Lecture Notes in Computer Science, S. 92-102. Springer, 2006.
    Zusammenfassung anzeigen
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    In Proceedings of FCT 2007, Band 4639 von Lecture Notes in Computer Science, S. 328--340. Springer, 2007.
    Zusammenfassung anzeigen
  • Andreas Jakoby, Till Tantau:
    Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
    In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Band 4855 von Lecture Notes in Computer Science, S. 216-227. Springer, 2007.
    Zusammenfassung anzeigen
  • Bodo Manthey, Till Tantau:
    Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
    In Proceedings of MFCS 2008, Band 5162 von Lecture Notes in Computer Science, S. 467-478. Springer, 2008.
    Zusammenfassung anzeigen
  • Max Bannach, Malte Skambath, Till Tantau:
    On the Parallel Parameterized Complexity of MaxSAT Variants.
    In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), LIPIcs, 2022.
    Website anzeigen
  • Max Bannach, Zacharias Heinrich, Till Tantau, Rüdiger Reischuk:
    Dynamic Kernels for Hitting Sets and Set Packing.
    In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Band 214 von LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
    Website anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Malte Skambath, Till Tantau:
    Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
    In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs, 2020.
    Website anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Till Tantau:
    On the Descriptive Complexity of Color Coding.
    In Proceedings of STACS 2019, LIPIcs, LIPIcs, 2019.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Malte Skambath, Till Tantau:
    Towards Work-Efficient Parallel Parameterized Algorithms.
    In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), Springer, 2019.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Till Tantau:
    Computing Hitting Set Kernels By AC^0-Circuits.
    In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science, LIPIcs, 2018.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Till Tantau:
    Computing Kernels in Parallel: Lower and Upper Bounds.
    In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), LIPIcs, 2018.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)..
    In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), S. 4:1--4:4. DROPS, 2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Till Tantau:
    Parallel Multivariate Meta-Theorems.
    In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), LIPIcs, 2016.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Malte Skambath, Till Tantau:
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
    In GD 2016: Graph Drawing and Network Visualization, Band 9801 von LNCS, S. 572-586. Springer, 2016.
    Website anzeigen | Zusammenfassung anzeigen
  • Max Bannach, Christoph Stockhusen, Till Tantau:
    Fast Parallel Fixed-Parameter Algorithms via Color Coding.
    In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs, 2015.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
    In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Band 30 von Leibniz International Proceedings in Informatics (LIPIcs), S. 703-715. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
    Website anzeigen | Zusammenfassung anzeigen
  • 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
  • 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
  • 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), Band 14 von Leibniz International Proceedings in Informatics (LIPIcs), S. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 7535 von Lecture Notes in Computer Science, S. 206-217. Springer, 2012.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), S. 265-274. IEEE Computer Society, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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), S. 143-152. IEEE Computer Society, 2010.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 6129 von Lecture Notes in Computer Science, S. 177-189. Springer, 2010.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 5532 von Lecture Notes in Computer Science, S. 201-210. Springer, 2009.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 5162 von Lecture Notes in Computer Science, S. 299-310. Springer, 2008.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.
    In Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Band 2996 von Lecture Notes in Computer Science, S. 326-337. Springer, 2004.
    PDF anzeigen | Zusammenfassung anzeigen