Jan Dreier

54 papers A* 13A 4B 4Journal 31Unranked 2
YearRankTypeTitle / Venue / Authors
2026 J jnl
Efficient reversal of transductions of sparse graph classes.
CoRR
Jan Dreier, Jakub Gajarský, Michal Pilipczuk
2026 J jnl
Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity.
CoRR
Jan Dreier, Clemens Kuske
2026 J jnl
The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching.
CoRR
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
2025 A* conf
Approximate Evaluation of Quantitative Second Order Queries.
LICS
Jan Dreier, Robert Ganian, Thekla Hamm
2025 A* conf
Merge-Width and First-Order Model Checking.
STOC
Jan Dreier, Szymon Torunczyk
2025 J jnl
Merge-width and First-Order Model Checking.
CoRR
Jan Dreier, Szymon Torunczyk
2024 J jnl
Corrigendum to "Twin-width and generalized coloring numbers" [Discrete Math. 345 (3) (2022) 112746].
Discret. Math.
Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond
2024 A* conf
First-Order Model Checking on Monadically Stable Graph Classes.
FOCS
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk
2024 A* conf
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes.
STOC
Jan Dreier, Nikolas Mählmann, Szymon Torunczyk
2024 J jnl
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes.
CoRR
Jan Dreier, Nikolas Mählmann, Szymon Torunczyk
2024 J jnl
SAT backdoors: Depth beats size.
J. Comput. Syst. Sci.
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
2023 A* conf
A logic-based algorithmic meta-theorem for mim-width.
SODA
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
2023 J jnl
Approximate Evaluation of Quantitative Second Order Queries.
CoRR
Jan Dreier, Robert Ganian, Thekla Hamm
2023 J jnl
CSP beyond tractable constraint languages.
Constraints An Int. J.
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
2023 A conf
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond.
ESA
Jan Dreier, Daniel Mock, Peter Rossmanith
2023 J jnl
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond.
CoRR
Jan Dreier, Daniel Mock, Peter Rossmanith
2023 J jnl
First-Order Model Checking on Monadically Stable Graph Classes.
CoRR
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk
2023 A* conf
First-Order Model Checking on Structurally Sparse Graph Classes.
STOC
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
2023 J jnl
First-Order Model Checking on Structurally Sparse Graph Classes.
CoRR
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
2023 A* conf
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes.
ICALP
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk
2023 J jnl
Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes.
Log. Methods Comput. Sci.
Jan Dreier
2023 A* conf
Pseudorandom Finite Models.
LICS
Jan Dreier, Jamie Tucker-Foltz
2023 J jnl
Pseudorandom Finite Models.
CoRR
Jan Dreier, Jamie Tucker-Foltz
2022 J jnl
A logic-based algorithmic meta-theorem for mim-width.
CoRR
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
2022 A conf
CSP Beyond Tractable Constraint Languages.
CP
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
2022 B conf
Combinatorial and Algorithmic Aspects of Monadic Stability.
ISAAC
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny
2022 J jnl
Combinatorial and Algorithmic Aspects of Monadic Stability.
CoRR
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny
2022 J jnl
Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes.
CoRR
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk
2022 A* conf
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.
LICS
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk
2022 J jnl
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.
CoRR
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk
2022 A conf
SAT Backdoors: Depth Beats Size.
ESA
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
2022 J jnl
SAT Backdoors: Depth Beats Size.
CoRR
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
2022 A* conf
Treelike Decompositions for Transductions of Sparse Graphs.
LICS
Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk, Szymon Torunczyk
2022 J jnl
Treelike decompositions for transductions of sparse graphs.
CoRR
Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk, Szymon Torunczyk
2022 J jnl
Twin-width and generalized coloring numbers.
Discret. Math.
Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond
2021 A* conf
Approximate Evaluation of First-Order Counting Queries.
SODA
Jan Dreier, Peter Rossmanith
2021 A* conf
Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes.
LICS
Jan Dreier
2021 J jnl
Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes.
CoRR
Jan Dreier
2020 J jnl
Advice for Online Knapsack With Removable Items.
CoRR
Hans-Joachim Böckenhauer, Jan Dreier, Fabian Frei, Peter Rossmanith
2020 J jnl
Approximate Evaluation of First-Order Counting Queries.
CoRR
Jan Dreier, Peter Rossmanith
2020 J jnl
Complexity of independency and cliquy trees.
Discret. Appl. Math.
Katrin Casel, Jan Dreier, Henning Fernau, Moritz Gobbert, Philipp Kuinke, Fernando Sánchez Villaamil, Markus L. Schmid, Erik Jan van Leeuwen
2020 A conf
First-Order Model-Checking in Random Graphs and Complex Networks.
ESA
Jan Dreier, Philipp Kuinke, Peter Rossmanith
2020 J jnl
First-Order Model-Checking in Random Graphs and Complex Networks.
CoRR
Jan Dreier, Philipp Kuinke, Peter Rossmanith
2020 A* conf
Hard Problems on Random Graphs.
ICALP
Jan Dreier, Henri Lotze, Peter Rossmanith
2020 — conf
Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size.
APPROX-RANDOM
Jan Dreier, Philipp Kuinke, Peter Rossmanith
2019 B conf
Hardness of FO Model-Checking on Random Graphs.
IPEC
Jan Dreier, Peter Rossmanith
2019 — conf
Motif Counting in Preferential Attachment Graphs.
FSTTCS
Jan Dreier, Peter Rossmanith
2019 B conf
The Complexity of Packing Edge-Disjoint Paths.
IPEC
Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang
2019 J jnl
The Complexity of Packing Edge-Disjoint Paths.
CoRR
Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang
2018 B conf
Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications.
SOFSEM
Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith
2018 J jnl
The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness.
CoRR
Jan Dreier, Philipp Kuinke, Peter Rossmanith
2017 J jnl
Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application.
CoRR
Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith
2014 J jnl
Overlapping Communities in Complex Networks.
CoRR
Jan Dreier
2014 J jnl
Overlapping Communities in Social Networks.
CoRR
Jan Dreier, Philipp Kuinke, Rafael Przybylski, Felix Reidl, Peter Rossmanith, Somnath Sikdar