default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDStefan Kratsch
Person information
- affiliation: HU Berlin, Germany
- affiliation (former): TU Berlin, Germany
- affiliation (former): Max Planck Institute for Informatics, Saarbrücken, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j47]Eun Jung Kim
, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation II: Undirected Graphs. ACM Trans. Algorithms 20(2): 12 (2024)- [c77]Narek Bojikian, Stefan Kratsch:
A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. ICALP 2024: 29:1-29:18 - [i67]Narek Bojikian, Stefan Kratsch:
Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width. CoRR abs/2402.08046 (2024) - [i66]Stefan Kratsch, Van Bang Le:
On polynomial kernelization for Stable Cutset. CoRR abs/2407.02086 (2024) - 2023
- [j46]Stefan Kratsch, Florian Nelles:
Efficient parameterized algorithms for computing all-pairs shortest paths. Discret. Appl. Math. 341: 102-119 (2023) - [c76]Falko Hegerfeld, Stefan Kratsch:
Tight Algorithms for Connectivity Problems Parameterized by Clique-Width. ESA 2023: 59:1-59:19 - [c75]Stefan Kratsch, Pascal Kunz:
Approximate Turing Kernelization and Lower Bounds for Domination Problems. IPEC 2023: 32:1-32:17 - [c74]Vera Chekan, Stefan Kratsch:
Tight Algorithmic Applications of Clique-Width Generalizations. MFCS 2023: 35:1-35:15 - [c73]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA 2023: 3218-3228 - [c72]Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch:
Tight Bounds for Connectivity Problems Parameterized by Cutwidth. STACS 2023: 14:1-14:16 - [c71]Falko Hegerfeld, Stefan Kratsch:
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. WG 2023: 388-402 - [i65]Falko Hegerfeld, Stefan Kratsch:
Tight algorithms for connectivity problems parameterized by clique-width. CoRR abs/2302.03627 (2023) - [i64]Falko Hegerfeld, Stefan Kratsch:
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. CoRR abs/2302.14128 (2023) - [i63]Stefan Kratsch, Pascal Kunz:
Approximate Turing kernelization and lower bounds for domination problems. CoRR abs/2307.02241 (2023) - [i62]Vera Chekan, Stefan Kratsch:
Tight Algorithmic Applications of Clique-Width Generalizations. CoRR abs/2307.04628 (2023) - [i61]Narek Bojikian, Stefan Kratsch:
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width. CoRR abs/2307.14264 (2023) - 2022
- [j45]Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse:
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. SIAM J. Discret. Math. 36(3): 1955-1990 (2022) - [c70]Falko Hegerfeld, Stefan Kratsch:
Towards Exact Structural Thresholds for Parameterized Complexity. IPEC 2022: 17:1-17:20 - [c69]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Directed flow-augmentation. STOC 2022: 938-947 - [i60]Stefan Kratsch, Florian Nelles, Alexandre Simon:
On Triangle Counting Parameterized by Twin-Width. CoRR abs/2202.06708 (2022) - [i59]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. CoRR abs/2207.07422 (2022) - [i58]Stefan Kratsch, Florian Nelles:
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width. CoRR abs/2209.14429 (2022) - [i57]Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch:
Tight Bounds for Connectivity Problems Parameterized by Cutwidth. CoRR abs/2212.12385 (2022) - 2021
- [j44]Toni Böhnlein, Stefan Kratsch, Oliver Schaudt:
Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting. Math. Program. 187(1): 653-695 (2021) - [c68]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Solving hard cut problems via flow-augmentation. SODA 2021: 149-168 - [c67]Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge:
Optimal Discretization is Fixed-parameter Tractable. SODA 2021: 1702-1719 - [i56]Falko Hegerfeld, Stefan Kratsch:
Towards exact structural thresholds for parameterized complexity. CoRR abs/2107.06111 (2021) - [i55]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Directed flow-augmentation. CoRR abs/2111.03450 (2021) - 2020
- [j43]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted Directed Cuts. Algorithmica 82(8): 2135-2155 (2020) - [j42]Stefan Kratsch, Magnus Wahlström:
Representative Sets and Irrelevant Vertices: New Tools for Kernelization. J. ACM 67(3): 16:1-16:50 (2020) - [j41]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite graphs of small readability. Theor. Comput. Sci. 806: 402-415 (2020) - [c66]Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse:
Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA 2020: 60:1-60:23 - [c65]Falko Hegerfeld, Stefan Kratsch:
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space. STACS 2020: 29:1-29:16 - [c64]Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse:
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS 2020: 36:1-36:14 - [c63]Stefan Kratsch, Florian Nelles:
Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. STACS 2020: 38:1-38:15 - [e1]Fedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen:
Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Lecture Notes in Computer Science 12160, Springer 2020, ISBN 978-3-030-42070-3 [contents] - [d1]Narek Bojikian, Alexander van der Grinten, Falko Hegerfeld, Laurence Alec Kluge, Stefan Kratsch:
PACE-Challenge-2020-HU-Berlin-Exact-Track. Zenodo, 2020
- [i54]Stefan Kratsch, Florian Nelles:
Efficient parameterized algorithms for computing all-pairs shortest paths. CoRR abs/2001.04908 (2020) - [i53]Falko Hegerfeld, Stefan Kratsch:
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. CoRR abs/2001.05364 (2020) - [i52]Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge:
Optimal Discretization is Fixed-parameter Tractable. CoRR abs/2003.02475 (2020) - [i51]Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse:
Approximate Turing Kernelization for Problems Parameterized by Treewidth. CoRR abs/2004.12683 (2020) - [i50]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Solving hard cut problems via flow-augmentation. CoRR abs/2007.09018 (2020)
2010 – 2019
- 2019
- [j40]Yann Disser, Stefan Kratsch, Manuel Sorge:
The Minimum Feasible Tileset Problem. Algorithmica 81(3): 1126-1151 (2019) - [j39]Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge:
The parameterized complexity of the minimum shared edges problem. J. Comput. Syst. Sci. 106: 23-48 (2019) - [j38]Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge:
Assessing the computational complexity of multilayer subgraph detection. Netw. Sci. 7(2): 215-241 (2019) - [j37]Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson:
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. SIAM J. Discret. Math. 33(4): 2092-2110 (2019) - [c62]Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese:
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. ESA 2019: 53:1-53:16 - [c61]Falko Hegerfeld, Stefan Kratsch:
On Adaptive Algorithms for Maximum Matching. ICALP 2019: 71:1-71:16 - [c60]Eva-Maria C. Hols, Stefan Kratsch:
On Kernelization for Edge Dominating Set under Structural Parameters. STACS 2019: 36:1-36:18 - [i49]Eva-Maria C. Hols, Stefan Kratsch:
On Kernelization for Edge Dominating Set under Structural Parameters. CoRR abs/1901.03582 (2019) - [i48]Falko Hegerfeld, Stefan Kratsch:
On adaptive algorithms for maximum matching. CoRR abs/1904.11244 (2019) - [i47]Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse:
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. CoRR abs/1905.03631 (2019) - [i46]Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese:
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. CoRR abs/1906.10982 (2019) - 2018
- [j36]Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65(3): 12:1-12:46 (2018) - [j35]Eva-Maria C. Hols, Stefan Kratsch:
A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. 62(1): 63-92 (2018) - [j34]Stefan Kratsch:
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. 32(3): 1806-1839 (2018) - [j33]Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch:
Parameterized complexity of team formation in social networks. Theor. Comput. Sci. 717: 26-36 (2018) - [c59]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite Graphs of Small Readability. COCOON 2018: 467-479 - [c58]Stefan Kratsch, Florian Nelles:
Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. ESA 2018: 55:1-55:15 - [c57]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-Budgeted Directed Cuts. IPEC 2018: 18:1-18:14 - [i45]Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson:
The parameterized complexity of finding a 2-sphere in a simplicial complex. CoRR abs/1802.07175 (2018) - [i44]Stefan Kratsch, Florian Nelles:
Efficient and adaptive parameterized algorithms on modular decompositions. CoRR abs/1804.10173 (2018) - [i43]Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma:
Bipartite Graphs of Small Readability. CoRR abs/1805.04765 (2018) - [i42]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted directed cuts. CoRR abs/1810.06848 (2018) - [i41]Jérémy Barbay, Johannes Fischer, Stefan Kratsch, Srinivasa Rao Satti:
Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). Dagstuhl Reports 8(7): 44-61 (2018) - 2017
- [j32]Stefan Kratsch, Manuel Sorge:
On Kernelization and Approximation for the Vector Connectivity Problem. Algorithmica 79(1): 96-138 (2017) - [j31]Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen, O-joung Kwon, Seongmin Ok:
Characterizing width two for variants of treewidth. Discret. Appl. Math. 216: 29-46 (2017) - [j30]Stefan Kratsch, Pascal Schweitzer:
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Discret. Appl. Math. 216: 240-253 (2017) - [j29]Stefan Kratsch, Martin Milanic:
On the complexity of the identifiable subgraph problem, revisited. Discret. Appl. Math. 226: 78-86 (2017) - [j28]Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84: 1-10 (2017) - [c56]Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge:
Assessing the Computational Complexity of Multi-layer Subgraph Detection. CIAC 2017: 128-139 - [c55]Toni Böhnlein, Stefan Kratsch, Oliver Schaudt:
Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. ICALP 2017: 46:1-46:13 - [c54]Eva-Maria C. Hols, Stefan Kratsch:
Smaller Parameters for Vertex Cover Kernelization. IPEC 2017: 20:1-20:12 - [c53]Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson:
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. STACS 2017: 18:1-18:14 - [c52]Yann Disser, Stefan Kratsch:
Robust and Adaptive Search. STACS 2017: 26:1-26:14 - [i40]Yann Disser, Stefan Kratsch:
Robust and adaptive search. CoRR abs/1702.05932 (2017) - [i39]Eva-Maria C. Hols, Stefan Kratsch:
Smaller parameters for vertex cover kernelization. CoRR abs/1711.04604 (2017) - 2016
- [j27]Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma:
Finding Shortest Paths Between Graph Colourings. Algorithmica 75(2): 295-321 (2016) - [j26]Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström:
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. Algorithmica 75(2): 383-402 (2016) - [j25]Stefan Kratsch:
On polynomial kernels for sparse integer linear programs. J. Comput. Syst. Sci. 82(5): 758-766 (2016) - [j24]Stefan Kratsch, Geevarghese Philip, Saurabh Ray:
Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms 12(3): 40:1-40:16 (2016) - [j23]Stefan Kratsch, Dániel Marx, Magnus Wahlström:
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. ACM Trans. Comput. Theory 8(1): 1:1-1:28 (2016) - [c51]Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch:
Parameterized Complexity of Team Formation in Social Networks. AAIM 2016: 137-149 - [c50]Stefan Kratsch:
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. ESA 2016: 59:1-59:17 - [c49]Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen:
Preprocessing Under Uncertainty: Matroid Intersection. MFCS 2016: 35:1-35:14 - [c48]Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen:
Preprocessing Under Uncertainty. STACS 2016: 33:1-33:13 - [c47]Eva-Maria C. Hols, Stefan Kratsch:
A Randomized Polynomial Kernel for Subset Feedback Vertex Set. STACS 2016: 43:1-43:14 - [r2]Stefan Kratsch:
Kernelization, Polynomial Lower Bounds. Encyclopedia of Algorithms 2016: 1036-1039 - [r1]Stefan Kratsch:
Kernelization, Preprocessing for Treewidth. Encyclopedia of Algorithms 2016: 1040-1042 - [i38]Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge:
The Parameterized Complexity of the Minimum Shared Edges Problem. CoRR abs/1602.01739 (2016) - [i37]Stefan Kratsch, Martin Milanic:
On the complexity of the identifiable subgraph problem, revisited. CoRR abs/1603.06226 (2016) - [i36]Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge:
Assessing the Computational Complexity of Multi-Layer Subgraph Detection. CoRR abs/1604.07724 (2016) - [i35]Stefan Kratsch:
A randomized polynomial kernelization for Vertex Cover with a smaller parameter. CoRR abs/1611.06795 (2016) - 2015
- [j22]Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu:
A Completeness Theory for Polynomial (Turing) Kernelization. Algorithmica 71(3): 702-730 (2015) - [j21]Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243: 86-111 (2015) - [j20]René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger:
Approximability and parameterized complexity of multicover by c-intervals. Inf. Process. Lett. 115(10): 744-749 (2015) - [j19]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. SIAM J. Discret. Math. 29(1): 122-144 (2015) - [j18]Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger:
How to Put Through Your Agenda in Collective Binary Decisions. ACM Trans. Economics and Comput. 4(1): 5:1-5:28 (2015) - [c46]Bart M. P. Jansen, Stefan Kratsch:
A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA 2015: 779-791 - [c45]Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge:
The Parameterized Complexity of the Minimum Shared Edges Problem. FSTTCS 2015: 448-462 - [c44]Stefan Kratsch, Manuel Sorge:
On Kernelization and Approximation for the Vector Connectivity Problem. IPEC 2015: 377-388 - [c43]Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
Polynomial Kernels for Weighted Problems. MFCS (2) 2015: 287-298 - [c42]Stefan Fafianie, Stefan Kratsch:
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. MFCS (2) 2015: 299-310 - [c41]Stefan Fafianie, Stefan Kratsch:
An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem. SEA 2015: 367-378 - [i34]Stefan Fafianie, Stefan Kratsch:
A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. CoRR abs/1504.08235 (2015) - [i33]Bart M. P. Jansen, Stefan Kratsch:
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity. CoRR abs/1506.07729 (2015) - [i32]Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
Polynomial Kernels for Weighted Problems. CoRR abs/1507.03439 (2015) - [i31]Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen:
Preprocessing under uncertainty. CoRR abs/1510.05503 (2015) - [i30]Eva-Maria C. Hols, Stefan Kratsch:
A randomized polynomial kernel for Subset Feedback Vertex Set. CoRR abs/1512.02510 (2015) - 2014
- [j17]Stefan Kratsch:
Recent developments in kernelization: A survey. Bull. EATCS 113 (2014) - [j16]Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrej Suchý, Gerhard J. Woeginger:
A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. J. Artif. Intell. Res. 50: 409-446 (2014) - [j15]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. J. Comput. Syst. Sci. 80(7): 1430-1447 (2014) - [j14]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernelization Lower Bounds by Cross-Composition. SIAM J. Discret. Math. 28(1): 277-305 (2014) - [j13]Stefan Kratsch:
Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem. ACM Trans. Algorithms 10(4): 19:1-19:16 (2014) - [j12]Stefan Kratsch, Magnus Wahlström:
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. ACM Trans. Algorithms 10(4): 20:1-20:15 (2014) - [j11]Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique Cover and Graph Separation: New Incompressibility Results. ACM Trans. Comput. Theory 6(2): 6:1-6:19 (2014) - [j10]Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman:
Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs. ACM Trans. Comput. Theory 7(1): 4:1-4:18 (2014) - [c40]Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström:
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. IPEC 2014: 208-220 - [c39]Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma:
Finding Shortest Paths Between Graph Colourings. IPEC 2014: 221-233 - [c38]Stefan Kratsch, Vuong Anh Quyen:
On Kernels for Covering and Packing ILPs with Small Coefficients. IPEC 2014: 307-318 - [c37]Stefan Fafianie, Stefan Kratsch:
Streaming Kernelization. MFCS (2) 2014: 275-286 - [c36]Stefan Kratsch, Geevarghese Philip, Saurabh Ray:
Point Line Cover: The Easy Kernel is Essentially Tight. SODA 2014: 1596-1606 - [c35]Yann Disser, Stefan Kratsch, Manuel Sorge:
The Minimum Feasible Tileset Problem. WAOA 2014: 144-155 - [i29]Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma:
Colouring Reconfiguration Is Fixed-Parameter Tractable. CoRR abs/1403.6347 (2014) - [i28]Stefan Fafianie, Stefan Kratsch:
Streaming Kernelization. CoRR abs/1405.1356 (2014) - [i27]Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström:
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. CoRR abs/1409.7261 (2014) - [i26]Yann Disser, Stefan Kratsch, Manuel Sorge:
The Minimum Feasible Tileset problem. CoRR abs/1409.8524 (2014) - [i25]Stefan Kratsch, Manuel Sorge:
On Kernelization and Approximation for the Vector Connectivity Problem. CoRR abs/1410.8819 (2014) - [i24]Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, Peter Rossmanith:
Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). Dagstuhl Reports 4(11): 1-21 (2014) - 2013
- [j9]Stefan Kratsch, Frank Neumann:
Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem. Algorithmica 65(4): 754-771 (2013) - [j8]Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström:
Parameterized Two-Player Nash Equilibrium. Algorithmica 65(4): 802-816 (2013) - [j7]Stefan Kratsch, Magnus Wahlström:
Two edge modification problems without polynomial kernels. Discret. Optim. 10(3): 193-199 (2013) - [j6]Bart M. P. Jansen, Stefan Kratsch:
Data reduction for graph coloring problems. Inf. Comput. 231: 70-88 (2013) - [j5]Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter:
Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1): 39-49 (2013) - [j4]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. SIAM J. Discret. Math. 27(4): 2108-2142 (2013) - [j3]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel bounds for path and cycle problems. Theor. Comput. Sci. 511: 117-136 (2013) - [j2]Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch, Yngve Villanger:
Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci. 511: 172-180 (2013) - [c34]Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger:
How to Put through Your Agenda in Collective Binary Decisions. ADT 2013: 30-44 - [c33]Stefan Kratsch:
On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. ESA 2013: 647-658 - [c32]Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. ICALP (1) 2013: 196-207 - [c31]Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu:
A Completeness Theory for Polynomial (Turing) Kernelization. IPEC 2013: 202-215 - [c30]Dieter Kratsch, Stefan Kratsch:
The Jump Number Problem: Exact and Parameterized. IPEC 2013: 230-242 - [c29]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Tight bounds for Parameterized Complexity of Cluster Editing. STACS 2013: 32-43 - [c28]Stefan Kratsch:
On Polynomial Kernels for Sparse Integer Linear Programs. STACS 2013: 80-91 - [c27]Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast hamiltonicity checking via bases of perfect matchings. STOC 2013: 301-310 - [c26]Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen:
Fixed-Parameter Tractability and Characterizations of Small Special Treewidth. WG 2013: 88-99 - [i23]Stefan Kratsch:
On Polynomial Kernels for Sparse Integer Linear Programs. CoRR abs/1302.3494 (2013) - [i22]Stefan Kratsch:
On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. CoRR abs/1302.3496 (2013) - [i21]Stefan Kratsch, Geevarghese Philip, Saurabh Ray:
Point Line Cover: The Easy Kernel is Essentially Tight. CoRR abs/1307.2521 (2013) - 2012
- [j1]Stefan Kratsch:
Polynomial Kernelizations for MIN F+Π1 and MAX NP. Algorithmica 63(1-2): 532-550 (2012) - [c25]Robert Bredereck, Jiehua Chen, Sepp Hartung, Rolf Niedermeier, Ondrej Suchý, Stefan Kratsch:
A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. AAAI 2012: 1292-1298 - [c24]Stefan Kratsch, Magnus Wahlström:
Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS 2012: 450-459 - [c23]Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) 2012: 254-265 - [c22]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. ICALP (1) 2012: 581-593 - [c21]Stefan Kratsch, Magnus Wahlström:
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. SODA 2012: 94-103 - [c20]Stefan Kratsch:
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. SODA 2012: 114-122 - [c19]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel Bounds for Structural Parameterizations of Pathwidth. SWAT 2012: 352-363 - [c18]Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman:
Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. SWAT 2012: 364-375 - [c17]Stefan Kratsch, Pascal Schweitzer:
Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs. WG 2012: 34-45 - [i20]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-parameter tractability of multicut in directed acyclic graphs. CoRR abs/1202.5749 (2012) - [i19]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernelization Lower Bounds By Cross-Composition. CoRR abs/1206.5941 (2012) - [i18]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel Bounds for Structural Parameterizations of Pathwidth. CoRR abs/1207.4900 (2012) - [i17]Stefan Kratsch, Pascal Schweitzer:
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs. CoRR abs/1208.0142 (2012) - [i16]Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR abs/1211.1505 (2012) - [i15]Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast Hamiltonicity checking via bases of perfect matchings. CoRR abs/1211.1506 (2012) - 2011
- [c16]Bart M. P. Jansen, Stefan Kratsch:
Data Reduction for Graph Coloring Problems. FCT 2011: 90-101 - [c15]Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch, Yngve Villanger:
Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. FCT 2011: 240-251 - [c14]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. ICALP (1) 2011: 437-448 - [c13]Bart M. P. Jansen, Stefan Kratsch:
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. IPEC 2011: 132-144 - [c12]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel Bounds for Path and Cycle Problems. IPEC 2011: 145-158 - [c11]Jiong Guo, Iyad A. Kanj, Stefan Kratsch:
Safe Approximation and Its Relation to Kernelization. IPEC 2011: 169-180 - [c10]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Cross-Composition: A New Technique for Kernelization Lower Bounds. STACS 2011: 165-176 - [c9]Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström:
Parameterized Two-Player Nash Equilibrium. WG 2011: 215-226 - [i14]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. CoRR abs/1104.4217 (2011) - [i13]Bart M. P. Jansen, Stefan Kratsch:
Data Reduction for Graph Coloring Problems. CoRR abs/1104.4229 (2011) - [i12]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Kernel Bounds for Path and Cycle Problems. CoRR abs/1106.4141 (2011) - [i11]Stefan Kratsch, Magnus Wahlström:
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. CoRR abs/1107.3068 (2011) - [i10]Bart M. P. Jansen, Stefan Kratsch:
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. CoRR abs/1107.3658 (2011) - [i9]Stefan Kratsch:
Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. CoRR abs/1107.3704 (2011) - [i8]Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, Xi Wu:
Hierarchies of Inefficient Kernelizability. CoRR abs/1110.0976 (2011) - [i7]Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique cover and graph separation: New incompressibility results. CoRR abs/1111.0570 (2011) - [i6]Stefan Kratsch, Magnus Wahlström:
Representative sets and irrelevant vertices: New tools for kernelization. CoRR abs/1111.2195 (2011) - [i5]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Subexponential fixed-parameter tractability of cluster editing. CoRR abs/1112.4419 (2011) - 2010
- [b1]Stefan Kratsch:
Kernelization of generic problems: upper and lower bounds. Saarland University, 2010 - [c8]Stefan Kratsch, Magnus Wahlström:
Preprocessing of Min Ones Problems: A Dichotomy. ICALP (1) 2010: 653-665 - [c7]Stefan Kratsch, Dániel Marx, Magnus Wahlström:
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. MFCS 2010: 489-500 - [c6]Stefan Kratsch, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto:
Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation. PPSN (1) 2010: 204-213 - [c5]Stefan Kratsch, Pascal Schweitzer:
Isomorphism for Graphs of Bounded Feedback Vertex Set Number. SWAT 2010: 81-92 - [c4]Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter:
Bin Packing with Fixed Number of Bins Revisited. SWAT 2010: 260-272 - [i4]Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlström:
Parameterized Two-Player Nash Equilibrium. CoRR abs/1006.2063 (2010) - [i3]Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Cross-Composition: A New Technique for Kernelization Lower Bounds. CoRR abs/1011.4224 (2010)
2000 – 2009
- 2009
- [c3]Stefan Kratsch, Frank Neumann:
Fixed-parameter evolutionary algorithms and the vertex cover problem. GECCO 2009: 293-300 - [c2]Stefan Kratsch, Magnus Wahlström:
Two Edge Modification Problems without Polynomial Kernels. IWPEC 2009: 264-275 - [c1]Stefan Kratsch:
Polynomial Kernelizations for MIN F+Pi1 and MAX NP. STACS 2009: 601-612 - [i2]Stefan Kratsch:
Polynomial Kernelizations for $\MINF_1$ and $\MNP$. CoRR abs/0902.1835 (2009) - [i1]Stefan Kratsch, Magnus Wahlström:
Preprocessing of Min Ones Problems: A Dichotomy. CoRR abs/0910.4518 (2009)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-21 02:40 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
