Stephan Kreutzer

Orcid: 0009-0002-9409-5356

Affiliations:
  • Technische Universität Berlin, Germany


According to our database1, Stephan Kreutzer authored at least 106 papers between 1999 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Excluding a planar matching minor in bipartite graphs.
J. Comb. Theory B, January, 2024

Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem.
CoRR, 2024

Packing Even Directed Circuits Quarter-Integrally.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Edge-Disjoint Paths in Eulerian Digraphs.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023
A half-integral Erdős-Pósa theorem for directed odd cycles.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022
Directed Tangle Tree-Decompositions and Applications.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.
Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Differential Games, Locality, and Model Checking for FO Logic of Graphs.
Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2020
First-Order Interpretations of Bounded Expansion Classes.
ACM Trans. Comput. Log., 2020

Model-Checking on Ordered Structures.
ACM Trans. Comput. Log., 2020

The canonical directed tree decomposition and its applications to the directed disjoint paths problem.
CoRR, 2020

Computing Shrub-Depth Decompositions.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

The Directed Flat Wall Theorem.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes.
ACM Trans. Algorithms, 2019

Routing with congestion in acyclic digraphs.
Inf. Process. Lett., 2019

Algorithmic Properties of Sparse Digraphs.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Polynomial Planar Directed Grid Theorem.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Coloring and Covering Nowhere Dense Graphs.
SIAM J. Discret. Math., 2018

The Presburger Award 2018 - Laudatio for Aleksander Madry.
Bull. EATCS, 2018

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Digraphs of Bounded Width.
Proceedings of the Classes of Directed Graphs., 2018

2017
Deciding First-Order Properties of Nowhere Dense Graphs.
J. ACM, 2017

Matching Connectivity: On the Structure of Graphs with Perfect Matchings.
Electron. Notes Discret. Math., 2017

The Presburger Award for Young Scientists 2018 - Call for Nominations.
Bull. EATCS, 2017

Algorithmic Properties of Sparse Digraphs.
CoRR, 2017

Majority Colourings of Digraphs.
Electron. J. Comb., 2017

Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Current Trends and New Perspectives for First-Order Model Checking (Invited Talk).
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
Nowhere Crownful Classes of Directed Graphs.
Encyclopedia of Algorithms, 2016

Complexity and monotonicity results for domination games.
Theor. Comput. Sci., 2016

Graph operations on parity games and polynomial-time algorithms.
Theor. Comput. Sci., 2016

DAG-width is PSPACE-complete.
Theor. Comput. Sci., 2016

Preface.
Theory Comput. Syst., 2016

Directed elimination games.
Discret. Appl. Math., 2016

The Erdos-Posa Property for Directed Graphs.
CoRR, 2016

Kernelization and Sparseness: the Case of Dominating Set.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Generalised Colouring Numbers on Classes of Bounded Expansion.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
Colouring and Covering Nowhere Dense Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

The Directed Grid Theorem.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Graph Searching Games and Width Measures for Directed Graphs.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Towards the Graph Minor Theorems for Directed Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Directed Width Measures and Monotonicity of Directed Graph Searching.
CoRR, 2014

Kernelization and Sparseness: the case of Dominating Set.
CoRR, 2014

Decomposition Theorems and Model-Checking for the Modal $μ$-Calculus.
CoRR, 2014

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem.
Proceedings of the Symposium on Theory of Computing, 2014

An Excluded Grid Theorem for Digraphs with Forbidden Minors.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Vertex Disjoint Paths in Upward Planar Graphs.
Proceedings of the Computer Science - Theory and Applications, 2014

On Hanf-equivalence and the number of embeddings of small induced subgraphs.
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

Decomposition theorems and model-checking for the modal <i>μ</i>-calculus.
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

2013
Vertex Disjoint Path in Upward Planar Graphs.
CoRR, 2013

Packing directed cycles through a specified vertex set.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Quantitative Monadic Second-Order Logic.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Model Checking for Successor-Invariant First-Order Logic on Minor-Closed Graph Classes.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Characterisations of Nowhere Dense Graphs (Invited Talk).
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012
Foreword: Special Issue on Theory and Applications of Graph Searching Problems.
Theor. Comput. Sci., 2012

The dag-width of directed graphs.
J. Comb. Theory B, 2012

Linkless and Flat Embeddings in 3-Space.
Discret. Comput. Geom., 2012

On the Parameterized Intractability of Monadic Second-Order Logic
Log. Methods Comput. Sci., 2012

Directed nowhere dense classes of graphs.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

First-Order and Monadic Second-Order Model-Checking on Ordered Structures.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

2011
Digraph decompositions and monotonicity in digraph searching.
Theor. Comput. Sci., 2011

Special Issue on "Theory and Applications of Graph Searching Problems".
Theor. Comput. Sci., 2011

Theory and Applications of Graph Searching Problems (GRASTA 2011) (Dagstuhl Seminar 11071).
Dagstuhl Reports, 2011

Graph searching games.
Proceedings of the Lectures in Game Theory for Computer Scientists., 2011

Algorithmic meta-theorems.
Proceedings of the Finite and Algorithmic Model Theory., 2011

2010
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Extended Computation Tree Logic.
Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2010

Lower Bounds for the Complexity of Monadic Second-Order Logic.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Linkless and flat embeddings in 3-space and the unknot problem.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
Parameterized Complexity of First-Order Logic.
Electron. Colloquium Comput. Complex., 2009

Algorithmic Meta-Theorems.
Electron. Colloquium Comput. Complex., 2009

Domination Problems in Nowhere-Dense Classes of Graphs
CoRR, 2009

Distance <i>d</i>-Domination Games.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Domination Problems in Nowhere-Dense Classes.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

A Note on the Relation between Inflationary Fixpoints and Least Fixpoints of Higher Order.
Proceedings of the 6th Workshop on Fixed Points in Computer Science, 2009

On the Parameterised Intractability of Monadic Second-Order Logic.
Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

Reachability in Succinct and Parametric One-Counter Automata.
Proceedings of the CONCUR 2009 - Concurrency Theory, 20th International Conference, 2009

Methods for Algorithmic Meta Theorems.
Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008
Digraph measures: Kelly decompositions, games, and orderings.
Theor. Comput. Sci., 2008

Computing excluded minors.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On Datalog vs. LFP.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Non-regular fixed-point logics and games.
Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007
Generalising automaticity to modal properties of finite structures.
Theor. Comput. Sci., 2007

Locally Excluding a Minor.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Boundedness of Monadic FO over Acyclic Structures.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Model Theory Makes Formulas Large.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Backtracking games and inflationary fixed points.
Theor. Comput. Sci., 2006

DAG-Width and Parity Games.
Proceedings of the STACS 2006, 2006

Approximation Schemes for First-Order Definable Optimisation Problems.
Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005
An Extension of Muchnik's Theorem.
J. Log. Comput., 2005

The Expressive Power of Two-Variable Least Fixed-Point Logics.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Complexity of Independence-Friendly Fixpoint Logic.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004
Inflationary fixed points in modal logic.
ACM Trans. Comput. Log., 2004

Logik und Informatik.
it Inf. Technol., 2004

Expressive equivalence of least and inflationary fixed-point logic.
Ann. Pure Appl. Log., 2004

2003
Once upon a Time in a West - Determinacy, Definability, and Complexity of Path Games.
Proceedings of the Logic for Programming, 2003

Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002
Pure and applied fixed-point logics.
Proceedings of the Ausgezeichnete Informatikdissertationen 2002, 2002

Partial Fixed-Point Logic on Infinite Structures.
Proceedings of the Computer Science Logic, 16th International Workshop, 2002

Pure and applied fixed-point logics.
PhD thesis, 2002

2001
Operational Semantics for Fixed-Point Logics on Constraint Databases.
Proceedings of the Logic for Programming, 2001

Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls.
Proceedings of the Database Theory, 2001

2000
Fixed-Point Query Languages for Linear Constraint Databases.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

1999
Descriptive Complexity Theory for Constraint Databases.
Proceedings of the Computer Science Logic, 13th International Workshop, 1999


  Loading...