Stefan Kratsch

According to our database1, Stefan Kratsch authored at least 84 papers between 2009 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2020
Bipartite graphs of small readability.
Theor. Comput. Sci., 2020

Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space.
CoRR, 2020

Efficient parameterized algorithms for computing all-pairs shortest paths.
CoRR, 2020

2019
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex.
SIAM J. Discrete Math., 2019

Assessing the computational complexity of multilayer subgraph detection.
Network Science, 2019

The parameterized complexity of the minimum shared edges problem.
J. Comput. Syst. Sci., 2019

Elimination Distances, Blocking Sets, and Kernels for Vertex Cover.
CoRR, 2019

The Minimum Feasible Tileset Problem.
Algorithmica, 2019

On Kernelization for Edge Dominating Set under Structural Parameters.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

On Adaptive Algorithms for Maximum Matching.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Parameterized complexity of team formation in social networks.
Theor. Comput. Sci., 2018

A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter.
SIAM J. Discrete Math., 2018

A Randomized Polynomial Kernel for Subset Feedback Vertex Set.
Theory Comput. Syst., 2018

Fast Hamiltonicity Checking Via Bases of Perfect Matchings.
J. ACM, 2018

Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281).
Dagstuhl Reports, 2018

Multi-Budgeted Directed Cuts.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
Polynomial kernels for weighted problems.
J. Comput. Syst. Sci., 2017

Graph isomorphism for graph classes characterized by two forbidden induced subgraphs.
Discrete Applied Mathematics, 2017

On the complexity of the identifiable subgraph problem, revisited.
Discrete Applied Mathematics, 2017

Characterizing width two for variants of treewidth.
Discrete Applied Mathematics, 2017

On Kernelization and Approximation for the Vector Connectivity Problem.
Algorithmica, 2017

Robust and Adaptive Search.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Smaller Parameters for Vertex Cover Kernelization.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Assessing the Computational Complexity of Multi-layer Subgraph Detection.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016
Kernelization, Preprocessing for Treewidth.
Encyclopedia of Algorithms, 2016

Kernelization, Polynomial Lower Bounds.
Encyclopedia of Algorithms, 2016

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.
TOCT, 2016

Point Line Cover: The Easy Kernel is Essentially Tight.
ACM Trans. Algorithms, 2016

On polynomial kernels for sparse integer linear programs.
J. Comput. Syst. Sci., 2016

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem.
Algorithmica, 2016

Finding Shortest Paths Between Graph Colourings.
Algorithmica, 2016

Preprocessing Under Uncertainty.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Preprocessing Under Uncertainty: Matroid Intersection.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
How to Put Through Your Agenda in Collective Binary Decisions.
ACM Trans. Economics and Comput., 2015

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.
SIAM J. Discrete Math., 2015

Approximability and parameterized complexity of multicover by c-intervals.
Inf. Process. Lett., 2015

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.
Inf. Comput., 2015

A Completeness Theory for Polynomial (Turing) Kernelization.
Algorithmica, 2015

An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem.
Proceedings of the Experimental Algorithms - 14th International Symposium, 2015

A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity.
Proceedings of the Algorithms - ESA 2015, 2015

2014
Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs.
TOCT, 2014

Clique Cover and Graph Separation: New Incompressibility Results.
TOCT, 2014

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
ACM Trans. Algorithms, 2014

Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem.
ACM Trans. Algorithms, 2014

Kernelization Lower Bounds by Cross-Composition.
SIAM J. Discrete Math., 2014

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.
J. Comput. Syst. Sci., 2014

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
J. Artif. Intell. Res., 2014

Recent developments in kernelization: A survey.
Bulletin of the EATCS, 2014

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451).
Dagstuhl Reports, 2014

Colouring Reconfiguration Is Fixed-Parameter Tractable.
CoRR, 2014

Streaming Kernelization.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On Kernels for Covering and Packing ILPs with Small Coefficients.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013
Parameterized complexity of vertex deletion into perfect graph classes.
Theor. Comput. Sci., 2013

Kernel bounds for path and cycle problems.
Theor. Comput. Sci., 2013

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
SIAM J. Discrete Math., 2013

Bin packing with fixed number of bins revisited.
J. Comput. Syst. Sci., 2013

Data reduction for graph coloring problems.
Inf. Comput., 2013

Two edge modification problems without polynomial kernels.
Discrete Optimization, 2013

Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem.
Algorithmica, 2013

Parameterized Two-Player Nash Equilibrium.
Algorithmica, 2013

Fixed-Parameter Tractability and Characterizations of Small Special Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Tight bounds for Parameterized Complexity of Cluster Editing.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Jump Number Problem: Exact and Parameterized.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility.
Proceedings of the Algorithms - ESA 2013, 2013

2012
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
CoRR, 2012

Polynomial Kernelizations for MIN F+Π1 and MAX NP.
Algorithmica, 2012

Kernel Bounds for Structural Parameterizations of Pathwidth.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

Representative Sets and Irrelevant Vertices: New Tools for Kernelization.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011
Subexponential fixed-parameter tractability of cluster editing
CoRR, 2011

Hierarchies of Inefficient Kernelizability
CoRR, 2011

Cross-Composition: A New Technique for Kernelization Lower Bounds.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Safe Approximation and Its Relation to Kernelization.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

2010
Kernelization of generic problems: upper and lower bounds.
PhD thesis, 2010

Isomorphism for Graphs of Bounded Feedback Vertex Set Number.
Proceedings of the Algorithm Theory, 2010

Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation.
Proceedings of the Parallel Problem Solving from Nature, 2010

Preprocessing of Min Ones Problems: A Dichotomy.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Polynomial Kernelizations for $\MINF_1$ and $\MNP$
CoRR, 2009

Polynomial Kernelizations for MIN F+Pi1 and MAX NP.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009


  Loading...