Till Tantau

Bull. EATCS, 2024

Faster Graph Algorithms Through DAG Compression.

[BibT_eX]

[DOI]

Florian Andreas Marwitz

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

On the Descriptive Complexity of Vertex Deletion Problems.

[BibT_eX]

[DOI]

Florian Chudigiewitsch

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2023

Existential Second-Order Logic over Graphs: Parameterized Complexity.

[BibT_eX]

[DOI]

Florian Chudigiewitsch

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

2022

On the Parallel Parameterized Complexity of MaxSAT Variants.

[BibT_eX]

[DOI]

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

On the Satisfaction Probability of k-CNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2021

Informatik fürs Leben lernen.

[BibT_eX]

[DOI]

Proceedings of the 19. GI-Fachtagung Informatik und Schule, 2021

Dynamic Kernels for Hitting Sets and Set Packing.

[BibT_eX]

[DOI]

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

Work-sensitive Dynamic Complexity of Formal Languages.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computation Structures, 2021

2020

Computing Hitting Set Kernels By AC<sup>0</sup>-Circuits.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.

[BibT_eX]

[DOI]

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).

[BibT_eX]

[DOI]

Anna Gál

Rahul Santhanam

Dagstuhl Reports, 2019

Towards Work-Efficient Parallel Parameterized Algorithms.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation - 13th International Conference, 2019

On the Descriptive Complexity of Color Coding.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Computing Hitting Set Kernels By AC^0-Circuits.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Computing Kernels in Parallel: Lower and Upper Bounds.

[BibT_eX]

[DOI]

Christian Herzog né Hoffmann

Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Study Program "Robotics and Autonomous Systems" at the University of Lübeck.

[BibT_eX]

[DOI]

Philipp Rostalski

Proceedings of the 12th European Workshop on Microelectronics Education, 2018

2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.

[BibT_eX]

[DOI]

Algorithms, 2016

Parallel Multivariate Meta-Theorems.

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 24th International Symposium, 2016

2015

On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.

[BibT_eX]

[DOI]

Algorithmica, 2015

Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Fast Parallel Fixed-parameter Algorithms via Color Coding.

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2013

Completeness Results for Parameterized Space Classes.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2012

Smoothed analysis of left-to-right maxima with applications.

[BibT_eX]

[DOI]

Valentina Damerow

Bodo Manthey

ACM Trans. Algorithms, 2012

Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Where First-Order and Monadic Second-Order Logic Coincide.

[BibT_eX]

[DOI]

Martin Grohe

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

On the Space Complexity of Parameterized Problems.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

Graph Drawing in TikZ.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 20th International Symposium, 2012

2011

The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets.

[BibT_eX]

[DOI]

Proceedings of the Algorithms Unplugged, 2011

2010

Logspace Versions of the Theorems of Bodlaender and Courcelle.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2009

Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.

[BibT_eX]

[DOI]

Ilka Schnoor

Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

2008

Der One-Time-Pad-Algorithmus: Der einfachste und sicherste Verschlüsselungsalgorithmus.

[BibT_eX]

[DOI]

Proceedings of the Taschenbuch der Algorithmen, 2008

Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Fixed-Parameter Algorithms in Phylogenetics.

[BibT_eX]

[DOI]

Jens Gramm

Comput. J., 2008

Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.

[BibT_eX]

[DOI]

Bodo Manthey

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

2007

Haplotyping with missing data via perfect path phylogenies.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

On the Complexity of Kings.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Optimal Flow Distribution Among Multiple Channels with Unknown Capacities .

[BibT_eX]

[DOI]

Richard M. Karp

Till Nierhoff

Proceedings of the Theoretical Computer Science, 2006

2005

The Complexity of Finding Paths in Graphs with Bounded Independence Number.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Weak cardinality theorems.

[BibT_eX]

[DOI]

J. Symb. Log., 2005

Context-free languages can be accepted with absolutely no space overhead.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Proshanto Mukherji

Inf. Comput., 2005

Logspace Optimization Problems and Their Approximability Properties.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

On the reducibility of sets inside NP to sets with low information content.

[BibT_eX]

[DOI]

Mitsunori Ogihara

J. Comput. Syst. Sci., 2004

Aggregates with Component Size One Characterize Polynomial Space

[BibT_eX]

[DOI]

Lorenz Weizsäcker

Electron. Colloquium Comput. Complex., 2004

Overhead-Free Computation, DCFLs, and CFLs

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Proshanto Mukherji

CoRR, 2004

A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Jens Gramm

Till Nierhoff

Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

2003

Query complexity of membership comparable sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Partial information classes.

[BibT_eX]

[DOI]

SIGACT News, 2003

Logspace Optimisation Problems and their Approximation Properties

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.

[BibT_eX]

[DOI]

Proceedings of the Ausgezeichnete Informatikdissertationen 2003, 2003

Weak Cardinality Theorems for First-Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Computation with Absolutely No Space Overhead.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Proshanto Mukherji

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

On structural similarities of finite automata and Turing machine enumerability classes.

[BibT_eX]

[DOI]

Wissenschaft & Technik Verlag, ISBN: 978-3-89685-200-7, 2003

2002

A Note on the Power of Extra Queries to Membership Comparable Sets

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Comparing Verboseness for Finite Automata and Turing Machines.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Towards a Cardinality Theorem for Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

On Reachability in Graphs with Bounded Independence Number.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

A Note on the Complexity of the Reachability Problem for Tournaments

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000

On the Power of Extra Queries to Selective Languages

[BibT_eX]

[DOI]