Stefan Kratsch

212 papers A* 13A 22B 29C 2Misc 1Journal 125Unranked 16

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth. CoRR Stefan Kratsch
2026	J	`jnl`	Applications of flow-augmentation. Comput. Sci. Rev. Stefan Kratsch, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström
2026	J	`jnl`	Approximate Turing kernelization for problems parameterized by treewidth. J. Comput. Syst. Sci. Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2026	J	`jnl`	On polynomial kernelization for Stable Cutset. Discret. Appl. Math. Stefan Kratsch, Van Bang Le
2025	B	`conf`	Boundaried Kernelization via Representative Sets. IPEC Leonid Antipov, Stefan Kratsch
2025	J	`jnl`	Boundaried Kernelization via Representative Sets. CoRR Leonid Antipov, Stefan Kratsch
2025	B	`conf`	Boundaried Kernelization. WG Leonid Antipov, Stefan Kratsch
2025	J	`jnl`	Boundaried Kernelization. CoRR Leonid Antipov, Stefan Kratsch
2025	B	`conf`	Efficient Parameterized Approximation. WG Stefan Kratsch, Pascal Kunz
2025	J	`jnl`	Efficient parameterized approximation. CoRR Stefan Kratsch, Pascal Kunz
2025	J	`jnl`	Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints. SIAM J. Comput. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2025	J	`jnl`	Flow-augmentation I: Directed graphs. J. ACM Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2025	B	`conf`	Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width. IPEC Narek Bojikian, Stefan Kratsch
2025	J	`jnl`	Tight Bounds for Feedback Vertex Set Parameterized by Clique-width. CoRR Narek Bojikian, Stefan Kratsch
2025	A	`conf`	Tight Bounds for Some Classical Problems Parameterized by Cutwidth. ESA Narek Bojikian, Vera Chekan, Stefan Kratsch
2025	J	`jnl`	Tight Bounds for some Classical Problems Parameterized by Cutwidth. CoRR Narek Bojikian, Vera Chekan, Stefan Kratsch
2024	A*	`conf`	A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. ICALP Narek Bojikian, Stefan Kratsch
2024	J	`jnl`	Flow-augmentation II: Undirected Graphs. ACM Trans. Algorithms Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2024	B	`conf`	On Polynomial Kernelization for Stable Cutset. WG Stefan Kratsch, Van Bang Le
2024	J	`jnl`	On polynomial kernelization for Stable Cutset. CoRR Stefan Kratsch, Van Bang Le
2024	J	`jnl`	Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width. CoRR Narek Bojikian, Stefan Kratsch
2023	J	`jnl`	A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width. CoRR Narek Bojikian, Stefan Kratsch
2023	B	`conf`	Approximate Turing Kernelization and Lower Bounds for Domination Problems. IPEC Stefan Kratsch, Pascal Kunz
2023	J	`jnl`	Approximate Turing kernelization and lower bounds for domination problems. CoRR Stefan Kratsch, Pascal Kunz
2023	J	`jnl`	Efficient parameterized algorithms for computing all-pairs shortest paths. Discret. Appl. Math. Stefan Kratsch, Florian Nelles
2023	A*	`conf`	Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2023	B	`conf`	Tight Algorithmic Applications of Clique-Width Generalizations. MFCS Vera Chekan, Stefan Kratsch
2023	J	`jnl`	Tight Algorithmic Applications of Clique-Width Generalizations. CoRR Vera Chekan, Stefan Kratsch
2023	A	`conf`	Tight Algorithms for Connectivity Problems Parameterized by Clique-Width. ESA Falko Hegerfeld, Stefan Kratsch
2023	B	`conf`	Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. WG Falko Hegerfeld, Stefan Kratsch
2023	J	`jnl`	Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. CoRR Falko Hegerfeld, Stefan Kratsch
2023	A	`conf`	Tight Bounds for Connectivity Problems Parameterized by Cutwidth. STACS Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch
2023	J	`jnl`	Tight algorithms for connectivity problems parameterized by clique-width. CoRR Falko Hegerfeld, Stefan Kratsch
2022	A*	`conf`	Directed flow-augmentation. STOC Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2022	J	`jnl`	Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width. CoRR Stefan Kratsch, Florian Nelles
2022	J	`jnl`	Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. SIAM J. Discret. Math. Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2022	J	`jnl`	Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. CoRR Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2022	J	`jnl`	On Triangle Counting Parameterized by Twin-Width. CoRR Stefan Kratsch, Florian Nelles, Alexandre Simon
2022	J	`jnl`	Tight Bounds for Connectivity Problems Parameterized by Cutwidth. CoRR Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch
2022	B	`conf`	Towards Exact Structural Thresholds for Parameterized Complexity. IPEC Falko Hegerfeld, Stefan Kratsch
2021	J	`jnl`	Directed flow-augmentation. CoRR Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2021	A*	`conf`	Optimal Discretization is Fixed-parameter Tractable. SODA Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
2021	J	`jnl`	Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting. Math. Program. Toni Böhnlein, Stefan Kratsch, Oliver Schaudt
2021	A*	`conf`	Solving hard cut problems via flow-augmentation. SODA Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2021	J	`jnl`	Towards exact structural thresholds for parameterized complexity. CoRR Falko Hegerfeld, Stefan Kratsch
2020	A	`conf`	Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2020	J	`jnl`	Approximate Turing Kernelization for Problems Parameterized by Treewidth. CoRR Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2020	J	`jnl`	Bipartite graphs of small readability. Theor. Comput. Sci. Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2020	A	`conf`	Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. STACS Stefan Kratsch, Florian Nelles
2020	J	`jnl`	Efficient parameterized algorithms for computing all-pairs shortest paths. CoRR Stefan Kratsch, Florian Nelles
2020	A	`conf`	Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2020	J	`jnl`	Multi-budgeted Directed Cuts. Algorithmica Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
2020	J	`jnl`	Optimal Discretization is Fixed-parameter Tractable. CoRR Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
2020	J	`jnl`	Representative Sets and Irrelevant Vertices: New Tools for Kernelization. J. ACM Stefan Kratsch, Magnus Wahlström
2020	A	`conf`	Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space. STACS Falko Hegerfeld, Stefan Kratsch
2020	J	`jnl`	Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. CoRR Falko Hegerfeld, Stefan Kratsch
2020	J	`jnl`	Solving hard cut problems via flow-augmentation. CoRR Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
2020	—	`ed.`	Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday Treewidth, Kernels, and Algorithms Fedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen
2019	J	`jnl`	Assessing the computational complexity of multilayer subgraph detection. Netw. Sci. Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
2019	J	`jnl`	Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. CoRR Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
2019	A*	`conf`	On Adaptive Algorithms for Maximum Matching. ICALP Falko Hegerfeld, Stefan Kratsch
2019	A	`conf`	On Kernelization for Edge Dominating Set under Structural Parameters. STACS Eva-Maria C. Hols, Stefan Kratsch
2019	J	`jnl`	On Kernelization for Edge Dominating Set under Structural Parameters. CoRR Eva-Maria C. Hols, Stefan Kratsch
2019	J	`jnl`	On adaptive algorithms for maximum matching. CoRR Falko Hegerfeld, Stefan Kratsch
2019	A	`conf`	Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. ESA Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
2019	J	`jnl`	Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. CoRR Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
2019	J	`jnl`	The Minimum Feasible Tileset Problem. Algorithmica Yann Disser, Stefan Kratsch, Manuel Sorge
2019	J	`jnl`	The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. SIAM J. Discret. Math. Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
2019	J	`jnl`	The parameterized complexity of the minimum shared edges problem. J. Comput. Syst. Sci. Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
2018	J	`jnl`	A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. Eva-Maria C. Hols, Stefan Kratsch
2018	J	`jnl`	A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. Stefan Kratsch
2018	Misc	`conf`	Bipartite Graphs of Small Readability. COCOON Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018	J	`jnl`	Bipartite Graphs of Small Readability. CoRR Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018	A	`conf`	Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. ESA Stefan Kratsch, Florian Nelles
2018	J	`jnl`	Efficient and adaptive parameterized algorithms on modular decompositions. CoRR Stefan Kratsch, Florian Nelles
2018	J	`jnl`	Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM Marek Cygan, Stefan Kratsch, Jesper Nederlof
2018	B	`conf`	Multi-Budgeted Directed Cuts. IPEC Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
2018	J	`jnl`	Multi-budgeted directed cuts. CoRR Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
2018	J	`jnl`	Parameterized complexity of team formation in social networks. Theor. Comput. Sci. Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch
2018	J	`jnl`	Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). Dagstuhl Reports Jérémy Barbay, Johannes Fischer, Stefan Kratsch, Srinivasa Rao Satti
2018	J	`jnl`	The parameterized complexity of finding a 2-sphere in a simplicial complex. CoRR Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
2017	C	`conf`	Assessing the Computational Complexity of Multi-layer Subgraph Detection. CIAC Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
2017	J	`jnl`	Characterizing width two for variants of treewidth. Discret. Appl. Math. Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen, O-joung Kwon, Seongmin Ok
2017	J	`jnl`	Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Discret. Appl. Math. Stefan Kratsch, Pascal Schweitzer
2017	J	`jnl`	On Kernelization and Approximation for the Vector Connectivity Problem. Algorithmica Stefan Kratsch, Manuel Sorge
2017	J	`jnl`	On the complexity of the identifiable subgraph problem, revisited. Discret. Appl. Math. Stefan Kratsch, Martin Milanic
2017	J	`jnl`	Polynomial kernels for weighted problems. J. Comput. Syst. Sci. Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin
2017	A*	`conf`	Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. ICALP Toni Böhnlein, Stefan Kratsch, Oliver Schaudt
2017	A	`conf`	Robust and Adaptive Search. STACS Yann Disser, Stefan Kratsch
2017	J	`jnl`	Robust and adaptive search. CoRR Yann Disser, Stefan Kratsch
2017	B	`conf`	Smaller Parameters for Vertex Cover Kernelization. IPEC Eva-Maria C. Hols, Stefan Kratsch
2017	J	`jnl`	Smaller parameters for vertex cover kernelization. CoRR Eva-Maria C. Hols, Stefan Kratsch
2017	A	`conf`	The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. STACS Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
2016	A	`conf`	A Randomized Polynomial Kernel for Subset Feedback Vertex Set. STACS Eva-Maria C. Hols, Stefan Kratsch
2016	A	`conf`	A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. ESA Stefan Kratsch
2016	J	`jnl`	A randomized polynomial kernelization for Vertex Cover with a smaller parameter. CoRR Stefan Kratsch
2016	J	`jnl`	Assessing the Computational Complexity of Multi-Layer Subgraph Detection. CoRR Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
2016	J	`jnl`	Finding Shortest Paths Between Graph Colourings. Algorithmica Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
2016	—	`ch.`	Kernelization, Polynomial Lower Bounds. Encyclopedia of Algorithms Stefan Kratsch
2016	—	`ch.`	Kernelization, Preprocessing for Treewidth. Encyclopedia of Algorithms Stefan Kratsch
2016	J	`jnl`	On polynomial kernels for sparse integer linear programs. J. Comput. Syst. Sci. Stefan Kratsch
2016	J	`jnl`	On the complexity of the identifiable subgraph problem, revisited. CoRR Stefan Kratsch, Martin Milanic
2016	J	`jnl`	Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. ACM Trans. Comput. Theory Stefan Kratsch, Dániel Marx, Magnus Wahlström
2016	C	`conf`	Parameterized Complexity of Team Formation in Social Networks. AAIM Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch
2016	J	`jnl`	Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms Stefan Kratsch, Geevarghese Philip, Saurabh Ray
2016	J	`jnl`	Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. Algorithmica Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström
2016	A	`conf`	Preprocessing Under Uncertainty. STACS Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
2016	B	`conf`	Preprocessing Under Uncertainty: Matroid Intersection. MFCS Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen
2016	J	`jnl`	The Parameterized Complexity of the Minimum Shared Edges Problem. CoRR Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
2015	J	`jnl`	A Completeness Theory for Polynomial (Turing) Kernelization. Algorithmica Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu
2015	—	`conf`	A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. MFCS (2) Stefan Fafianie, Stefan Kratsch
2015	A	`conf`	A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA Bart M. P. Jansen, Stefan Kratsch
2015	J	`jnl`	A randomized polynomial kernel for Subset Feedback Vertex Set. CoRR Eva-Maria C. Hols, Stefan Kratsch
2015	J	`jnl`	A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. CoRR Stefan Fafianie, Stefan Kratsch
2015	J	`jnl`	A structural approach to kernels for ILPs: Treewidth and Total Unimodularity. CoRR Bart M. P. Jansen, Stefan Kratsch
2015	B	`conf`	An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem. SEA Stefan Fafianie, Stefan Kratsch
2015	J	`jnl`	Approximability and parameterized complexity of multicover by c-intervals. Inf. Process. Lett. René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger
2015	J	`jnl`	Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2015	J	`jnl`	Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. SIAM J. Discret. Math. Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2015	J	`jnl`	How to Put Through Your Agenda in Collective Binary Decisions. ACM Trans. Economics and Comput. Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger
2015	B	`conf`	On Kernelization and Approximation for the Vector Connectivity Problem. IPEC Stefan Kratsch, Manuel Sorge
2015	—	`conf`	Polynomial Kernels for Weighted Problems. MFCS (2) Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin
2015	J	`jnl`	Polynomial Kernels for Weighted Problems. CoRR Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin
2015	J	`jnl`	Preprocessing under uncertainty. CoRR Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
2015	—	`conf`	The Parameterized Complexity of the Minimum Shared Edges Problem. FSTTCS Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
2014	J	`jnl`	A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. J. Artif. Intell. Res. Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrej Suchý, Gerhard J. Woeginger
2014	J	`jnl`	Clique Cover and Graph Separation: New Incompressibility Results. ACM Trans. Comput. Theory Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2014	J	`jnl`	Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem. ACM Trans. Algorithms Stefan Kratsch
2014	J	`jnl`	Colouring Reconfiguration Is Fixed-Parameter Tractable. CoRR Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
2014	J	`jnl`	Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. ACM Trans. Algorithms Stefan Kratsch, Magnus Wahlström
2014	B	`conf`	Finding Shortest Paths Between Graph Colourings. IPEC Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
2014	J	`jnl`	Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs. ACM Trans. Comput. Theory Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman
2014	J	`jnl`	Kernelization Lower Bounds by Cross-Composition. SIAM J. Discret. Math. Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2014	J	`jnl`	On Kernelization and Approximation for the Vector Connectivity Problem. CoRR Stefan Kratsch, Manuel Sorge
2014	B	`conf`	On Kernels for Covering and Packing ILPs with Small Coefficients. IPEC Stefan Kratsch, Vuong Anh Quyen
2014	J	`jnl`	Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). Dagstuhl Reports Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, Peter Rossmanith
2014	A*	`conf`	Point Line Cover: The Easy Kernel is Essentially Tight. SODA Stefan Kratsch, Geevarghese Philip, Saurabh Ray
2014	B	`conf`	Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. IPEC Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström
2014	J	`jnl`	Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. CoRR Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström
2014	J	`jnl`	Recent developments in kernelization: A survey. Bull. EATCS Stefan Kratsch
2014	—	`conf`	Streaming Kernelization. MFCS (2) Stefan Fafianie, Stefan Kratsch
2014	J	`jnl`	Streaming Kernelization. CoRR Stefan Fafianie, Stefan Kratsch
2014	B	`conf`	The Minimum Feasible Tileset Problem. WAOA Yann Disser, Stefan Kratsch, Manuel Sorge
2014	J	`jnl`	The Minimum Feasible Tileset problem. CoRR Yann Disser, Stefan Kratsch, Manuel Sorge
2014	J	`jnl`	Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. J. Comput. Syst. Sci. Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger
2013	B	`conf`	A Completeness Theory for Polynomial (Turing) Kernelization. IPEC Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu
2013	J	`jnl`	Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter
2013	J	`jnl`	Data reduction for graph coloring problems. Inf. Comput. Bart M. P. Jansen, Stefan Kratsch
2013	—	`conf`	Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. ICALP (1) Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2013	A*	`conf`	Fast hamiltonicity checking via bases of perfect matchings. STOC Marek Cygan, Stefan Kratsch, Jesper Nederlof
2013	J	`jnl`	Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem. Algorithmica Stefan Kratsch, Frank Neumann
2013	B	`conf`	Fixed-Parameter Tractability and Characterizations of Small Special Treewidth. WG Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen
2013	—	`conf`	How to Put through Your Agenda in Collective Binary Decisions. ADT Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger
2013	J	`jnl`	Kernel bounds for path and cycle problems. Theor. Comput. Sci. Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2013	J	`jnl`	On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility CoRR Stefan Kratsch
2013	A	`conf`	On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. ESA Stefan Kratsch
2013	J	`jnl`	On Polynomial Kernels for Sparse Integer Linear Programs CoRR Stefan Kratsch
2013	A	`conf`	On Polynomial Kernels for Sparse Integer Linear Programs. STACS Stefan Kratsch
2013	J	`jnl`	Parameterized Two-Player Nash Equilibrium. Algorithmica Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström
2013	J	`jnl`	Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci. Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch, Yngve Villanger
2013	J	`jnl`	Point Line Cover: The Easy Kernel is Essentially Tight. CoRR Stefan Kratsch, Geevarghese Philip, Saurabh Ray
2013	J	`jnl`	Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. SIAM J. Discret. Math. Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2013	B	`conf`	The Jump Number Problem: Exact and Parameterized. IPEC Dieter Kratsch, Stefan Kratsch
2013	A	`conf`	Tight bounds for Parameterized Complexity of Cluster Editing. STACS Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger
2013	J	`jnl`	Two edge modification problems without polynomial kernels. Discret. Optim. Stefan Kratsch, Magnus Wahlström
2012	A*	`conf`	A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. AAAI Robert Bredereck, Jiehua Chen, Sepp Hartung, Rolf Niedermeier, Ondrej Suchý, Stefan Kratsch
2012	—	`conf`	Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2012	A*	`conf`	Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. SODA Stefan Kratsch
2012	A*	`conf`	Compression via matroids: a randomized polynomial kernel for odd cycle transversal. SODA Stefan Kratsch, Magnus Wahlström
2012	J	`jnl`	Fast Hamiltonicity checking via bases of perfect matchings CoRR Marek Cygan, Stefan Kratsch, Jesper Nederlof
2012	—	`conf`	Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. ICALP (1) Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2012	J	`jnl`	Fixed-parameter tractability of multicut in directed acyclic graphs CoRR Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2012	B	`conf`	Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs. WG Stefan Kratsch, Pascal Schweitzer
2012	J	`jnl`	Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs CoRR Stefan Kratsch, Pascal Schweitzer
2012	J	`jnl`	Kernel Bounds for Structural Parameterizations of Pathwidth CoRR Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2012	—	`conf`	Kernel Bounds for Structural Parameterizations of Pathwidth. SWAT Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2012	—	`conf`	Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. SWAT Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman
2012	J	`jnl`	Kernelization Lower Bounds By Cross-Composition CoRR Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2012	J	`jnl`	Polynomial Kernelizations for MIN F+Π1 and MAX NP. Algorithmica Stefan Kratsch
2012	A*	`conf`	Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS Stefan Kratsch, Magnus Wahlström
2012	J	`jnl`	Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time CoRR Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
2011	J	`jnl`	Clique cover and graph separation: New incompressibility results CoRR Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
2011	J	`jnl`	Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem CoRR Stefan Kratsch
2011	J	`jnl`	Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal CoRR Stefan Kratsch, Magnus Wahlström
2011	A	`conf`	Cross-Composition: A New Technique for Kernelization Lower Bounds. STACS Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2011	J	`jnl`	Data Reduction for Graph Coloring Problems CoRR Bart M. P. Jansen, Stefan Kratsch
2011	B	`conf`	Data Reduction for Graph Coloring Problems. FCT Bart M. P. Jansen, Stefan Kratsch
2011	J	`jnl`	Hierarchies of Inefficient Kernelizability CoRR Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu
2011	J	`jnl`	Kernel Bounds for Path and Cycle Problems CoRR Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2011	B	`conf`	Kernel Bounds for Path and Cycle Problems. IPEC Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2011	J	`jnl`	On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal CoRR Bart M. P. Jansen, Stefan Kratsch
2011	B	`conf`	On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. IPEC Bart M. P. Jansen, Stefan Kratsch
2011	B	`conf`	Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. FCT Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch, Yngve Villanger
2011	B	`conf`	Parameterized Two-Player Nash Equilibrium. WG Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström
2011	J	`jnl`	Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization CoRR Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2011	—	`conf`	Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. ICALP (1) Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2011	J	`jnl`	Representative sets and irrelevant vertices: New tools for kernelization CoRR Stefan Kratsch, Magnus Wahlström
2011	B	`conf`	Safe Approximation and Its Relation to Kernelization. IPEC Jiong Guo, Iyad A. Kanj, Stefan Kratsch
2011	J	`jnl`	Subexponential fixed-parameter tractability of cluster editing CoRR Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger
2010	—	`conf`	Bin Packing with Fixed Number of Bins Revisited. SWAT Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter
2010	J	`jnl`	Cross-Composition: A New Technique for Kernelization Lower Bounds CoRR Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
2010	—	`conf`	Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation. PPSN (1) Stefan Kratsch, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto
2010	—	`conf`	Isomorphism for Graphs of Bounded Feedback Vertex Set Number. SWAT Stefan Kratsch, Pascal Schweitzer
2010	—	`—`	Kernelization of generic problems: upper and lower bounds. Stefan Kratsch
2010	B	`conf`	Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. MFCS Stefan Kratsch, Dániel Marx, Magnus Wahlström
2010	J	`jnl`	Parameterized Two-Player Nash Equilibrium CoRR Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström
2010	—	`conf`	Preprocessing of Min Ones Problems: A Dichotomy. ICALP (1) Stefan Kratsch, Magnus Wahlström
2009	A	`conf`	Fixed-parameter evolutionary algorithms and the vertex cover problem. GECCO Stefan Kratsch, Frank Neumann
2009	J	`jnl`	Polynomial Kernelizations for $\MINF_1$ and $\MNP$ CoRR Stefan Kratsch
2009	A	`conf`	Polynomial Kernelizations for MIN F STACS Stefan Kratsch
2009	J	`jnl`	Preprocessing of Min Ones Problems: A Dichotomy CoRR Stefan Kratsch, Magnus Wahlström
2009	—	`conf`	Two Edge Modification Problems without Polynomial Kernels. IWPEC Stefan Kratsch, Magnus Wahlström