Stephan Kreutzer

According to our database, Stephan Kreutzer authored at least 105 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Excluding a planar matching minor in bipartite graphs.

Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht

J. Comb. Theory, Ser. B, January, 2024

Edge-Disjoint Paths in Eulerian Digraphs.

Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer

CoRR, 2024

2023

Packing even directed circuits quarter-integrally.

Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht

CoRR, 2023

A half-integral Erdős-Pósa theorem for directed odd cycles.

Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Directed Tangle Tree-Decompositions and Applications.

Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.

Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk

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.

Jakub Gajarský, Maximilian Gorsky, Stephan Kreutzer

Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2020

First-Order Interpretations of Bounded Expansion Classes.

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

ACM Trans. Comput. Log., 2020

Model-Checking on Ordered Structures.

Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz

ACM Trans. Comput. Log., 2020

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

Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon

CoRR, 2020

Computing Shrub-Depth Decompositions.

Jakub Gajarský, Stephan Kreutzer

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

The Directed Flat Wall Theorem.

Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes.

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

ACM Trans. Algorithms, 2019

Routing with congestion in acyclic digraphs.

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich

Inf. Process. Lett., 2019

Algorithmic Properties of Sparse Digraphs.

Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

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

Polynomial Planar Directed Grid Theorem.

Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Coloring and Covering Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos

SIAM J. Discret. Math., 2018

The Presburger Award 2018 - Laudatio for Aleksander Madry.

Stephan Kreutzer

Bull. EATCS, 2018

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface.

Albert Atserias, Stephan Kreutzer, Marc Noy

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Digraphs of Bounded Width.

Stephan Kreutzer, O-joung Kwon

Proceedings of the Classes of Directed Graphs., 2018

2017

Deciding First-Order Properties of Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

J. ACM, 2017

Matching Connectivity: On the Structure of Graphs with Perfect Matchings.

Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht

Electron. Notes Discret. Math., 2017

The Presburger Award for Young Scientists 2018 - Call for Nominations.

Stephan Kreutzer

Bull. EATCS, 2017

Algorithmic Properties of Sparse Digraphs.

Stephan Kreutzer, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

CoRR, 2017

Majority Colourings of Digraphs.

Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, David R. Wood

Electron. J. Comb., 2017

Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs.

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Grischa Weberstädt

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.

Jan van den Heuvel, Stephan Kreutzer, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs.

Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Current Trends and New Perspectives for First-Order Model Checking (Invited Talk).

Stephan Kreutzer

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Nowhere Crownful Classes of Directed Graphs.

Stephan Kreutzer

Encyclopedia of Algorithms, 2016

Complexity and monotonicity results for domination games.

Stephan Kreutzer, Sebastian Ordyniak

Theor. Comput. Sci., 2016

Graph operations on parity games and polynomial-time algorithms.

Christoph Dittmann, Stephan Kreutzer, Alexandru I. Tomescu

Theor. Comput. Sci., 2016

DAG-width is PSPACE-complete.

Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich

Theor. Comput. Sci., 2016

Preface.

Andrei Bulatov, Stephan Kreutzer

Theory Comput. Syst., 2016

Directed elimination games.

Viktor Engelmann, Sebastian Ordyniak, Stephan Kreutzer

Discret. Appl. Math., 2016

The Erdos-Posa Property for Directed Graphs.

Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, Paul Wollan

CoRR, 2016

Kernelization and Sparseness: the Case of Dominating Set.

Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Generalised Colouring Numbers on Classes of Bounded Expansion.

Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Colouring and Covering Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

The Directed Grid Theorem.

Ken-ichi Kawarabayashi, Stephan Kreutzer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Graph Searching Games and Width Measures for Directed Graphs.

Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

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

Towards the Graph Minor Theorems for Directed Graphs.

Ken-ichi Kawarabayashi, Stephan Kreutzer

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Directed Width Measures and Monotonicity of Directed Graph Searching.

Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

CoRR, 2014

Kernelization and Sparseness: the case of Dominating Set.

Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Somnath Sikdar

CoRR, 2014

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

Mikolaj Bojanczyk, Christoph Dittmann, Stephan Kreutzer

CoRR, 2014

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem.

Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer

Proceedings of the Symposium on Theory of Computing, 2014

An Excluded Grid Theorem for Digraphs with Forbidden Minors.

Ken-ichi Kawarabayashi, Stephan Kreutzer

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Vertex Disjoint Paths in Upward Planar Graphs.

Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz

Proceedings of the Computer Science - Theory and Applications, 2014

On Hanf-equivalence and the number of embeddings of small induced subgraphs.

Stephan Kreutzer, Nicole Schweikardt

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.

Mikolaj Bojanczyk, Christoph Dittmann, Stephan Kreutzer

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.

Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz

CoRR, 2013

Packing directed cycles through a specified vertex set.

Ken-ichi Kawarabayashi, Daniel Král', Marek Krcál, Stephan Kreutzer

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Quantitative Monadic Second-Order Logic.

Stephan Kreutzer, Cristian Riveros

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.

Kord Eickmeyer, Ken-ichi Kawarabayashi, Stephan Kreutzer

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Characterisations of Nowhere Dense Graphs (Invited Talk).

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

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.

Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos

Theor. Comput. Sci., 2012

The dag-width of directed graphs.

Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, Jan Obdrzálek

J. Comb. Theory, Ser. B, 2012

Linkless and Flat Embeddings in 3-Space.

Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar

Discret. Comput. Geom., 2012

On the Parameterized Intractability of Monadic Second-Order Logic

Stephan Kreutzer

Log. Methods Comput. Sci., 2012

Directed nowhere dense classes of graphs.

Stephan Kreutzer, Siamak Tazari

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

First-Order and Monadic Second-Order Model-Checking on Ordered Structures.

Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz

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

2011

Digraph decompositions and monotonicity in digraph searching.

Stephan Kreutzer, Sebastian Ordyniak

Theor. Comput. Sci., 2011

Special Issue on "Theory and Applications of Graph Searching Problems".

Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos

Theor. Comput. Sci., 2011

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

Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos

Dagstuhl Reports, 2011

Graph searching games.

Stephan Kreutzer

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

Algorithmic meta-theorems.

Stephan Kreutzer

Proceedings of the Finite and Algorithmic Model Theory., 2011

2010

On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic.

Stephan Kreutzer, Siamak Tazari

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Extended Computation Tree Logic.

Roland Axelsson, Matthew Hague, Stephan Kreutzer, Martin Lange, Markus Latte

Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2010

Lower Bounds for the Complexity of Monadic Second-Order Logic.

Stephan Kreutzer, Siamak Tazari

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Linkless and flat embeddings in 3-space and the unknot problem.

Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

Parameterized Complexity of First-Order Logic.

Stephan Kreutzer, Anuj Dawar

Electron. Colloquium Comput. Complex., 2009

Algorithmic Meta-Theorems.

Stephan Kreutzer

Electron. Colloquium Comput. Complex., 2009

Domination Problems in Nowhere-Dense Classes of Graphs

Anuj Dawar, Stephan Kreutzer

CoRR, 2009

Distance <i>d</i>-Domination Games.

Stephan Kreutzer, Sebastian Ordyniak

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Domination Problems in Nowhere-Dense Classes.

Anuj Dawar, Stephan Kreutzer

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.

Stephan Kreutzer, Martin Lange

Proceedings of the 6th Workshop on Fixed Points in Computer Science, 2009

On the Parameterised Intractability of Monadic Second-Order Logic.

Stephan Kreutzer

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

Reachability in Succinct and Parametric One-Counter Automata.

Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell

Proceedings of the CONCUR 2009 - Concurrency Theory, 20th International Conference, 2009

Methods for Algorithmic Meta Theorems.

Martin Grohe, Stephan Kreutzer

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

Digraph measures: Kelly decompositions, games, and orderings.

Paul Hunter, Stephan Kreutzer

Theor. Comput. Sci., 2008

Computing excluded minors.

Isolde Adler, Martin Grohe, Stephan Kreutzer

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On Datalog vs. LFP.

Anuj Dawar, Stephan Kreutzer

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Non-regular fixed-point logics and games.

Stephan Kreutzer, Martin Lange

Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007

Generalising automaticity to modal properties of finite structures.

Anuj Dawar, Stephan Kreutzer

Theor. Comput. Sci., 2007

Locally Excluding a Minor.

Anuj Dawar, Martin Grohe, Stephan Kreutzer

Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Boundedness of Monadic FO over Acyclic Structures.

Stephan Kreutzer, Martin Otto, Nicole Schweikardt

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Model Theory Makes Formulas Large.

Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

Backtracking games and inflationary fixed points.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

Theor. Comput. Sci., 2006

DAG-Width and Parity Games.

Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer

Proceedings of the STACS 2006, 2006

Approximation Schemes for First-Order Definable Optimisation Problems.

Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005

An Extension of Muchnik's Theorem.

Achim Blumensath, Stephan Kreutzer

J. Log. Comput., 2005

The Expressive Power of Two-Variable Least Fixed-Point Logics.

Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Complexity of Independence-Friendly Fixpoint Logic.

Julian C. Bradfield, Stephan Kreutzer

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004

Inflationary fixed points in modal logic.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

ACM Trans. Comput. Log., 2004

Logik und Informatik.

Stephan Kreutzer, Nicole Schweikardt

it Inf. Technol., 2004

Expressive equivalence of least and inflationary fixed-point logic.

Stephan Kreutzer

Ann. Pure Appl. Log., 2004

2003

Once upon a Time in a West - Determinacy, Definability, and Complexity of Path Games.

Dietmar Berwanger, Erich Grädel, Stephan Kreutzer

Proceedings of the Logic for Programming, 2003

Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions.

Erich Grädel, Stephan Kreutzer

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002

Pure and applied fixed-point logics.

Stephan Kreutzer

Proceedings of the Ausgezeichnete Informatikdissertationen 2002, 2002

Partial Fixed-Point Logic on Infinite Structures.

Stephan Kreutzer

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

Pure and applied fixed-point logics.

Stephan Kreutzer

PhD thesis, 2002

2001

Operational Semantics for Fixed-Point Logics on Constraint Databases.

Stephan Kreutzer

Proceedings of the Logic for Programming, 2001

Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls.

Stephan Kreutzer

Proceedings of the Database Theory, 2001

2000

Fixed-Point Query Languages for Linear Constraint Databases.

Stephan Kreutzer

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

1999

Descriptive Complexity Theory for Constraint Databases.

Erich Grädel, Stephan Kreutzer

Proceedings of the Computer Science Logic, 13th International Workshop, 1999