×
Compute Distance To:
Author ID: kratsch.stefan Recent zbMATH articles by "Kratsch, Stefan"
Published as: Kratsch, Stefan
Homepage: http://hu.berlin/kratsch
External Links: MGP · ORCID · Google Scholar · dblp · GND
Documents Indexed: 100 Publications since 2009
1 Contribution as Editor
Reviewing Activity: 1 Review
Co-Authors: 73 Co-Authors with 91 Joint Publications
2,534 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

81 Publications have been cited 704 times in 484 Documents Cited by Year
Kernelization lower bounds by cross-composition. Zbl 1295.05222
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
99
2014
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1327.68126
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
55
2015
Cross-composition: a new technique for kernelization lower bounds. Zbl 1230.68085
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
39
2011
Bin packing with fixed number of bins revisited. Zbl 1261.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
30
2013
Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Zbl 1311.68076
Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
22
2014
Two edge modification problems without polynomial kernels. Zbl 1273.68181
Kratsch, Stefan; Wahlström, Magnus
21
2009
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1293.05288
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
20
2013
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1296.68074
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
19
2013
Data reduction for graph coloring problems. Zbl 1435.68124
Jansen, Bart M. P.; Kratsch, Stefan
17
2013
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
17
2014
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1333.68204
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
14
2011
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
14
2016
Isomorphism for graphs of bounded feedback vertex set number. Zbl 1284.05296
Kratsch, Stefan; Schweitzer, Pascal
13
2010
A completeness theory for polynomial (Turing) kernelization. Zbl 1312.68102
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
13
2015
Two edge modification problems without polynomial kernels. Zbl 06920189
Kratsch, Stefan; Wahlström, Magnus
13
2013
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1326.05053
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
12
2015
Preprocessing of min ones problems: a dichotomy. Zbl 1288.68132
Kratsch, Stefan; Wahlström, Magnus
11
2010
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1290.05143
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Kernel bounds for path and cycle problems. Zbl 1407.68207
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Parameterized complexity of vertex deletion into perfect graph classes. Zbl 1407.68223
Heggernes, Pinar; van ’t Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve
11
2013
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
11
2018
Recent developments in kernelization: a survey. Zbl 1409.68144
Kratsch, Stefan
11
2014
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Zbl 1341.05168
Kratsch, Stefan; Schweitzer, Pascal
10
2012
Point line cover: the easy kernel is essentially tight. Zbl 1423.68547
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
10
2016
Kernel bounds for structural parameterizations of pathwidth. Zbl 1357.68078
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
9
2012
Data reduction for graph coloring problems. Zbl 1342.68167
Jansen, Bart M. P.; Kratsch, Stefan
8
2011
Parameterized complexity of vertex deletion into perfect graph classes. Zbl 1342.68165
Heggernes, Pinar; van’t Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve
8
2011
Fixed-parameter evolutionary algorithms and the vertex cover problem. Zbl 1262.68180
Kratsch, Stefan; Neumann, Frank
7
2013
Polynomial kernels for weighted problems. Zbl 1353.68122
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
7
2017
Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. Zbl 1287.68077
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
7
2010
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
A shortcut to (sun)flowers: kernels in logarithmic space or linear time. Zbl 1465.68111
Fafianie, Stefan; Kratsch, Stefan
7
2015
A structural approach to kernels for ILPs: treewidth and total unimodularity. Zbl 1466.68046
Jansen, Bart M. P.; Kratsch, Stefan
7
2015
Streaming kernelization. Zbl 1426.68120
Fafianie, Stefan; Kratsch, Stefan
7
2014
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 1491.68092
Kratsch, Stefan; Wahlström, Magnus
7
2020
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
6
2014
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1397.68103
Kratsch, Stefan
6
2016
Parameterized two-player Nash equilibrium. Zbl 1272.68142
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
5
2013
Tight bounds for parameterized complexity of cluster editing. Zbl 1354.68119
Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
5
2013
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
5
2018
The parameterized complexity of the minimum shared edges problem. Zbl 1366.68090
Fluschnik, Till; Kratsch, Stefan; Niedermeier, Rolf; Sorge, Manuel
5
2015
Kernel bounds for path and cycle problems. Zbl 1352.68092
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
5
2012
Bin packing with fixed number of bins revisited. Zbl 1285.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
4
2010
On polynomial kernels for integer linear programs: covering, packing and feasibility. Zbl 1394.68188
Kratsch, Stefan
4
2013
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1272.68158
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
4
2012
Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP. Zbl 1236.68097
Kratsch, Stefan
4
2012
A multivariate complexity analysis of lobbying in multiple referenda. Zbl 1342.91011
Bredereck, Robert; Chen, Jiehua; Hartung, Sepp; Kratsch, Stefan; Niedermeier, Rolf; Suchý, Ondřej; Woeginger, Gerhard J.
4
2014
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1396.68059
Kratsch, Stefan
3
2018
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1423.68217
Kratsch, Stefan; Wahlström, Magnus
3
2012
Point line cover: the easy kernel is essentially tight. Zbl 1423.68548
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
3
2014
On polynomial kernels for sparse integer linear programs. Zbl 1338.68111
Kratsch, Stefan
3
2016
Characterizing width two for variants of treewidth. Zbl 1350.05116
Bodlaender, Hans L.; Kratsch, Stefan; Kreuzen, Vincent J. C.; Kwon, O-joung; Ok, Seongmin
3
2017
Clique cover and graph separation: new incompressibility results. Zbl 1272.68152
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
3
2012
On polynomial kernels for structural parameterizations of odd cycle transversal. Zbl 1352.68112
Jansen, Bart M. P.; Kratsch, Stefan
3
2012
A completeness theory for polynomial (Turing) kernelization. Zbl 1407.68224
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
3
2013
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1423.68216
Kratsch, Stefan
2
2012
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2014
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Zbl 1350.05105
Kratsch, Stefan; Schweitzer, Pascal
2
2017
Approximability and parameterized complexity of multicover by \(c\)-intervals. Zbl 1329.68149
van Bevern, René; Chen, Jiehua; Hüffner, Falk; Kratsch, Stefan; Talmon, Nimrod; Woeginger, Gerhard J.
2
2015
On kernels for covering and packing ILPs with small coefficients. Zbl 1456.68068
Kratsch, Stefan; Quyen, Vuong Anh
2
2014
Polynomial kernels for weighted problems. Zbl 1353.68121
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
2
2015
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1357.68073
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2012
On kernelization and approximation for the vector connectivity problem. Zbl 1372.68137
Kratsch, Stefan; Sorge, Manuel
2
2015
Safe approximation and its relation to kernelization. Zbl 1352.68108
Guo, Jiong; Kanj, Iyad; Kratsch, Stefan
2
2012
Fixed-parameter tractability and characterizations of small special treewidth. Zbl 1400.05234
Bodlaender, Hans L.; Kratsch, Stefan; Kreuzen, Vincent J. C.
2
2013
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1398.68249
Kratsch, Stefan
2
2014
Smaller parameters for vertex cover kernelization. Zbl 1443.68072
Hols, Eva-Maria C.; Kratsch, Stefan
2
2018
Efficient and adaptive parameterized algorithms on modular decompositions. Zbl 07378725
Kratsch, Stefan; Nelles, Florian
1
2018
Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
1
2016
Polynomial kernels and user reductions for the workflow satisfiability problem. Zbl 1350.68143
Gutin, Gregory; Kratsch, Stefan; Wahlström, Magnus
1
2016
On polynomial kernels for sparse integer linear programs. Zbl 1354.68127
Kratsch, Stefan
1
2013
A randomized polynomial kernel for subset feedback vertex set. Zbl 1380.68225
Hols, Eva-Maria C.; Kratsch, Stefan
1
2016
Assessing the computational complexity of multi-layer subgraph detection. Zbl 1486.68126
Bredereck, Robert; Komusiewicz, Christian; Kratsch, Stefan; Molter, Hendrik; Niedermeier, Rolf; Sorge, Manuel
1
2017
The minimum feasible tileset problem. Zbl 1417.68285
Disser, Yann; Kratsch, Stefan; Sorge, Manuel
1
2015
The parameterized complexity of finding a 2-sphere in a simplicial complex. Zbl 1402.68084
Burton, Benjamin; Cabello, Sergio; Kratsch, Stefan; Pettersson, William
1
2017
Robust and adaptive search. Zbl 1402.68035
Disser, Yann; Kratsch, Stefan
1
2017
Parameterized two-player Nash equilibrium. Zbl 1341.05160
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
1
2011
How to put through your agenda in collective binary decisions. Zbl 1406.91099
Alon, Noga; Bredereck, Robert; Chen, Jiehua; Kratsch, Stefan; Niedermeier, Rolf; Woeginger, Gerhard J.
1
2013
Bipartite graphs of small readability. Zbl 1442.05183
Chikhi, Rayan; Jovičić, Vladan; Kratsch, Stefan; Medvedev, Paul; Milanič, Martin; Raskhodnikova, Sofya; Varma, Nithin
1
2018
Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting. Zbl 1441.91018
Böhnlein, Toni; Kratsch, Stefan; Schaudt, Oliver
1
2017
The parameterized complexity of finding a 2-sphere in a simplicial complex. Zbl 1432.57051
Burton, Benjamin; Cabello, Sergio; Kratsch, Stefan; Pettersson, William
1
2019
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 1491.68092
Kratsch, Stefan; Wahlström, Magnus
7
2020
The parameterized complexity of finding a 2-sphere in a simplicial complex. Zbl 1432.57051
Burton, Benjamin; Cabello, Sergio; Kratsch, Stefan; Pettersson, William
1
2019
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
11
2018
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
5
2018
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1396.68059
Kratsch, Stefan
3
2018
Smaller parameters for vertex cover kernelization. Zbl 1443.68072
Hols, Eva-Maria C.; Kratsch, Stefan
2
2018
Efficient and adaptive parameterized algorithms on modular decompositions. Zbl 07378725
Kratsch, Stefan; Nelles, Florian
1
2018
Bipartite graphs of small readability. Zbl 1442.05183
Chikhi, Rayan; Jovičić, Vladan; Kratsch, Stefan; Medvedev, Paul; Milanič, Martin; Raskhodnikova, Sofya; Varma, Nithin
1
2018
Polynomial kernels for weighted problems. Zbl 1353.68122
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
7
2017
Characterizing width two for variants of treewidth. Zbl 1350.05116
Bodlaender, Hans L.; Kratsch, Stefan; Kreuzen, Vincent J. C.; Kwon, O-joung; Ok, Seongmin
3
2017
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Zbl 1350.05105
Kratsch, Stefan; Schweitzer, Pascal
2
2017
Assessing the computational complexity of multi-layer subgraph detection. Zbl 1486.68126
Bredereck, Robert; Komusiewicz, Christian; Kratsch, Stefan; Molter, Hendrik; Niedermeier, Rolf; Sorge, Manuel
1
2017
The parameterized complexity of finding a 2-sphere in a simplicial complex. Zbl 1402.68084
Burton, Benjamin; Cabello, Sergio; Kratsch, Stefan; Pettersson, William
1
2017
Robust and adaptive search. Zbl 1402.68035
Disser, Yann; Kratsch, Stefan
1
2017
Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting. Zbl 1441.91018
Böhnlein, Toni; Kratsch, Stefan; Schaudt, Oliver
1
2017
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
14
2016
Point line cover: the easy kernel is essentially tight. Zbl 1423.68547
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
10
2016
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1397.68103
Kratsch, Stefan
6
2016
On polynomial kernels for sparse integer linear programs. Zbl 1338.68111
Kratsch, Stefan
3
2016
Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
1
2016
Polynomial kernels and user reductions for the workflow satisfiability problem. Zbl 1350.68143
Gutin, Gregory; Kratsch, Stefan; Wahlström, Magnus
1
2016
A randomized polynomial kernel for subset feedback vertex set. Zbl 1380.68225
Hols, Eva-Maria C.; Kratsch, Stefan
1
2016
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1327.68126
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
55
2015
A completeness theory for polynomial (Turing) kernelization. Zbl 1312.68102
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
13
2015
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1326.05053
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
12
2015
A shortcut to (sun)flowers: kernels in logarithmic space or linear time. Zbl 1465.68111
Fafianie, Stefan; Kratsch, Stefan
7
2015
A structural approach to kernels for ILPs: treewidth and total unimodularity. Zbl 1466.68046
Jansen, Bart M. P.; Kratsch, Stefan
7
2015
The parameterized complexity of the minimum shared edges problem. Zbl 1366.68090
Fluschnik, Till; Kratsch, Stefan; Niedermeier, Rolf; Sorge, Manuel
5
2015
Approximability and parameterized complexity of multicover by \(c\)-intervals. Zbl 1329.68149
van Bevern, René; Chen, Jiehua; Hüffner, Falk; Kratsch, Stefan; Talmon, Nimrod; Woeginger, Gerhard J.
2
2015
Polynomial kernels for weighted problems. Zbl 1353.68121
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
2
2015
On kernelization and approximation for the vector connectivity problem. Zbl 1372.68137
Kratsch, Stefan; Sorge, Manuel
2
2015
The minimum feasible tileset problem. Zbl 1417.68285
Disser, Yann; Kratsch, Stefan; Sorge, Manuel
1
2015
Kernelization lower bounds by cross-composition. Zbl 1295.05222
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
99
2014
Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Zbl 1311.68076
Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
22
2014
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
17
2014
Recent developments in kernelization: a survey. Zbl 1409.68144
Kratsch, Stefan
11
2014
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Streaming kernelization. Zbl 1426.68120
Fafianie, Stefan; Kratsch, Stefan
7
2014
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
6
2014
A multivariate complexity analysis of lobbying in multiple referenda. Zbl 1342.91011
Bredereck, Robert; Chen, Jiehua; Hartung, Sepp; Kratsch, Stefan; Niedermeier, Rolf; Suchý, Ondřej; Woeginger, Gerhard J.
4
2014
Point line cover: the easy kernel is essentially tight. Zbl 1423.68548
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
3
2014
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2014
On kernels for covering and packing ILPs with small coefficients. Zbl 1456.68068
Kratsch, Stefan; Quyen, Vuong Anh
2
2014
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1398.68249
Kratsch, Stefan
2
2014
Bin packing with fixed number of bins revisited. Zbl 1261.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
30
2013
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1293.05288
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
20
2013
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1296.68074
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
19
2013
Data reduction for graph coloring problems. Zbl 1435.68124
Jansen, Bart M. P.; Kratsch, Stefan
17
2013
Two edge modification problems without polynomial kernels. Zbl 06920189
Kratsch, Stefan; Wahlström, Magnus
13
2013
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1290.05143
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Kernel bounds for path and cycle problems. Zbl 1407.68207
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Parameterized complexity of vertex deletion into perfect graph classes. Zbl 1407.68223
Heggernes, Pinar; van ’t Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve
11
2013
Fixed-parameter evolutionary algorithms and the vertex cover problem. Zbl 1262.68180
Kratsch, Stefan; Neumann, Frank
7
2013
Parameterized two-player Nash equilibrium. Zbl 1272.68142
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
5
2013
Tight bounds for parameterized complexity of cluster editing. Zbl 1354.68119
Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
5
2013
On polynomial kernels for integer linear programs: covering, packing and feasibility. Zbl 1394.68188
Kratsch, Stefan
4
2013
A completeness theory for polynomial (Turing) kernelization. Zbl 1407.68224
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
3
2013
Fixed-parameter tractability and characterizations of small special treewidth. Zbl 1400.05234
Bodlaender, Hans L.; Kratsch, Stefan; Kreuzen, Vincent J. C.
2
2013
On polynomial kernels for sparse integer linear programs. Zbl 1354.68127
Kratsch, Stefan
1
2013
How to put through your agenda in collective binary decisions. Zbl 1406.91099
Alon, Noga; Bredereck, Robert; Chen, Jiehua; Kratsch, Stefan; Niedermeier, Rolf; Woeginger, Gerhard J.
1
2013
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Zbl 1341.05168
Kratsch, Stefan; Schweitzer, Pascal
10
2012
Kernel bounds for structural parameterizations of pathwidth. Zbl 1357.68078
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
9
2012
Kernel bounds for path and cycle problems. Zbl 1352.68092
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
5
2012
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1272.68158
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
4
2012
Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP. Zbl 1236.68097
Kratsch, Stefan
4
2012
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1423.68217
Kratsch, Stefan; Wahlström, Magnus
3
2012
Clique cover and graph separation: new incompressibility results. Zbl 1272.68152
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
3
2012
On polynomial kernels for structural parameterizations of odd cycle transversal. Zbl 1352.68112
Jansen, Bart M. P.; Kratsch, Stefan
3
2012
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1423.68216
Kratsch, Stefan
2
2012
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1357.68073
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2012
Safe approximation and its relation to kernelization. Zbl 1352.68108
Guo, Jiong; Kanj, Iyad; Kratsch, Stefan
2
2012
Cross-composition: a new technique for kernelization lower bounds. Zbl 1230.68085
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
39
2011
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1333.68204
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
14
2011
Data reduction for graph coloring problems. Zbl 1342.68167
Jansen, Bart M. P.; Kratsch, Stefan
8
2011
Parameterized complexity of vertex deletion into perfect graph classes. Zbl 1342.68165
Heggernes, Pinar; van’t Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve
8
2011
Parameterized two-player Nash equilibrium. Zbl 1341.05160
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
1
2011
Isomorphism for graphs of bounded feedback vertex set number. Zbl 1284.05296
Kratsch, Stefan; Schweitzer, Pascal
13
2010
Preprocessing of min ones problems: a dichotomy. Zbl 1288.68132
Kratsch, Stefan; Wahlström, Magnus
11
2010
Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. Zbl 1287.68077
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
7
2010
Bin packing with fixed number of bins revisited. Zbl 1285.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
4
2010
Two edge modification problems without polynomial kernels. Zbl 1273.68181
Kratsch, Stefan; Wahlström, Magnus
21
2009
all top 5

Cited by 580 Authors

40 Saurabh, Saket
37 Jansen, Bart M. P.
36 Kratsch, Stefan
29 Pilipczuk, Marcin L.
25 Pilipczuk, Michał
20 Lokshtanov, Daniel
19 Bodlaender, Hans L.
19 Raman, Venkatesh
19 Sau, Ignasi
18 Cygan, Marek
18 Marx, Dániel
17 Fomin, Fedor V.
17 Niedermeier, Rolf
16 Komusiewicz, Christian
14 Golovach, Petr A.
13 Paulusma, Daniël
12 Panolan, Fahad
12 Suchý, Ondřej
12 Thilikos, Dimitrios M.
12 Wahlström, Magnus
11 Nichterlein, André
11 Sorge, Manuel
11 van Bevern, René
11 Van Leeuwen, Erik Jan
10 Gutin, Gregory Z.
10 Knop, Dušan
10 Mnich, Matthias
9 Bonnet, Edouard
9 Ganian, Robert
9 Hermelin, Danny
9 Koutecký, Martin
9 Majumdar, Diptapriyo
9 Molter, Hendrik
9 Pieterse, Astrid
8 Baste, Julien
8 Kwon, Ojoung
7 Eiben, Eduard
7 Misra, Neeldhara
7 Misra, Pranabendu
7 Perez, Anthony
7 Ramanujan, M. S.
7 Wrochna, Marcin
7 Zehavi, Meirav
6 Agrawal, Akanksha
6 Fellows, Michael Ralph
6 Heggernes, Pinar
6 Ito, Takehiro
6 Johnson, Matthew
6 Mertzios, George B.
6 Neumann, Frank
6 Ordyniak, Sebastian
6 Otachi, Yota
6 Paul, Christophe
6 Rai, Ashutosh
6 Suzuki, Akira
6 Thomassé, Stéphan
6 van ’t Hof, Pim
6 Villanger, Yngve
5 Bergougnoux, Benjamin
5 Bulteau, Laurent
5 Campos, Victor A.
5 Dabrowski, Konrad Kazimierz
5 Dell, Holger
5 Fluschnik, Till
5 Kanj, Iyad A.
5 Kolay, Sudeshna
5 Meesum, Syed Mohammad
5 Mouawad, Amer E.
5 Nederlof, Jesper
5 Sandeep, R. B.
5 Tale, Prafullkumar
5 Wang, Jianxin
5 Zhou, Xiao
4 Banik, Aritra
4 Bliznets, Ivan A.
4 Bonamy, Marthe
4 Bousquet, Nicolas
4 Bredereck, Robert
4 Brettell, Nick
4 de Berg, Mark Theodoor
4 dos Santos Souza, Uéverton
4 Drange, Pål Grønås
4 Hanaka, Tesshu
4 Kanté, Mamadou Moustapha
4 Kisfaludi-Bak, Sándor
4 Krithika, R.
4 Liedloff, Mathieu
4 Lopes, Raul H. C.
4 Luo, Junjie
4 Nishimura, Naomi
4 Schweitzer, Pascal
4 Souza, Uéverton S.
4 Szeider, Stefan
4 van der Zanden, Tom C.
4 Weller, Mathias
4 Ye, Junjie
4 Yeo, Anders
3 Araújo, Júlio César Silva
3 Ashok, Pradeesha
3 Bessy, Stéphane
...and 480 more Authors
all top 5

Cited in 49 Serials

94 Algorithmica
52 Theoretical Computer Science
33 Discrete Applied Mathematics
33 Journal of Computer and System Sciences
29 SIAM Journal on Discrete Mathematics
20 Theory of Computing Systems
13 SIAM Journal on Computing
11 Information Processing Letters
9 Journal of Combinatorial Optimization
8 Information and Computation
5 Discrete Optimization
5 ACM Transactions on Computation Theory
4 Journal of Scheduling
3 Artificial Intelligence
3 European Journal of Operational Research
3 Journal of Graph Algorithms and Applications
2 Acta Informatica
2 Journal of Combinatorial Theory. Series B
2 Operations Research Letters
2 Discrete & Computational Geometry
2 Mathematical Programming. Series A. Series B
2 ACM Journal of Experimental Algorithmics
2 Computer Science Review
1 Discrete Mathematics
1 Mathematics of Operations Research
1 European Journal of Combinatorics
1 Computers & Operations Research
1 Journal of Automated Reasoning
1 International Journal of Computational Geometry & Applications
1 Computational Geometry
1 International Journal of Foundations of Computer Science
1 Linear Algebra and its Applications
1 Distributed Computing
1 Computational Optimization and Applications
1 The Journal of Artificial Intelligence Research (JAIR)
1 Discussiones Mathematicae. Graph Theory
1 International Transactions in Operational Research
1 INFORMS Journal on Computing
1 Journal of the ACM
1 Data Mining and Knowledge Discovery
1 RAIRO. Operations Research
1 Journal of Discrete Algorithms
1 Oberwolfach Reports
1 Optimization Letters
1 Discrete Mathematics, Algorithms and Applications
1 Algorithms
1 Mathematical Programming Computation
1 Journal of the Operations Research Society of China
1 Bulletin of the Hellenic Mathematical Society

Citations by Year