×

zbMATH — the first resource for mathematics

Kratsch, Stefan

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: 96 Publications since 2009

Publications by Year

Citations contained in zbMATH Open

76 Publications have been cited 586 times in 397 Documents Cited by Year
Kernelization lower bounds by cross-composition. Zbl 1295.05222
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
85
2014
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1327.68126
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
40
2015
Cross-composition: a new technique for kernelization lower bounds. Zbl 1230.68085
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
38
2011
Bin packing with fixed number of bins revisited. Zbl 1261.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
21
2013
Two edge modification problems without polynomial kernels. Zbl 1273.68181
Kratsch, Stefan; Wahlström, Magnus
21
2009
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
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1293.05288
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
17
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
17
2014
Data reduction for graph coloring problems. Zbl 1435.68124
Jansen, Bart M. P.; Kratsch, Stefan
16
2013
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1333.68204
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
14
2011
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
13
2014
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
Kernel bounds for path and cycle problems. Zbl 1407.68207
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Isomorphism for graphs of bounded feedback vertex set number. Zbl 1284.05296
Kratsch, Stefan; Schweitzer, Pascal
11
2010
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
10
2013
Two edge modification problems without polynomial kernels. Zbl 06920189
Kratsch, Stefan; Wahlström, Magnus
10
2013
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
9
2016
Kernel bounds for structural parameterizations of pathwidth. Zbl 1357.68078
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
9
2012
A completeness theory for polynomial (Turing) kernelization. Zbl 1312.68102
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
9
2015
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
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1326.05053
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
7
2015
Recent developments in kernelization: a survey. Zbl 1409.68144
Kratsch, Stefan
7
2014
Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. Zbl 1287.68077
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
7
2010
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
6
2013
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
6
2018
Polynomial kernels for weighted problems. Zbl 1353.68122
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
6
2017
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
5
2014
A structural approach to kernels for ILPs: treewidth and total unimodularity. Zbl 1466.68046
Jansen, Bart M. P.; Kratsch, Stefan
5
2015
Tight bounds for parameterized complexity of cluster editing. Zbl 1354.68119
Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
5
2013
Parameterized two-player Nash equilibrium. Zbl 1272.68142
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
5
2013
Kernel bounds for path and cycle problems. Zbl 1352.68092
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
5
2012
A shortcut to (sun)flowers: kernels in logarithmic space or linear time. Zbl 1465.68111
Fafianie, Stefan; Kratsch, Stefan
4
2015
Streaming kernelization. Zbl 1426.68120
Fafianie, Stefan; Kratsch, Stefan
4
2014
The parameterized complexity of the minimum shared edges problem. Zbl 1366.68090
Fluschnik, Till; Kratsch, Stefan; Niedermeier, Rolf; Sorge, Manuel
4
2015
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1397.68103
Kratsch, Stefan
4
2016
Fixed-parameter evolutionary algorithms and the vertex cover problem. Zbl 1262.68180
Kratsch, Stefan; Neumann, Frank
4
2013
Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP. Zbl 1236.68097
Kratsch, Stefan
4
2012
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1272.68158
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
4
2012
On polynomial kernels for integer linear programs: covering, packing and feasibility. Zbl 1394.68188
Kratsch, Stefan
4
2013
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.
3
2014
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
Bin packing with fixed number of bins revisited. Zbl 1285.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
3
2010
On polynomial kernels for structural parameterizations of odd cycle transversal. Zbl 1352.68112
Jansen, Bart M. P.; Kratsch, Stefan
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 sparse integer linear programs. Zbl 1338.68111
Kratsch, Stefan
3
2016
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1423.68217
Kratsch, Stefan; Wahlström, Magnus
3
2012
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 07273087
Kratsch, Stefan; Wahlström, Magnus
3
2020
A completeness theory for polynomial (Turing) kernelization. Zbl 1407.68224
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
2
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 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
On kernelization and approximation for the vector connectivity problem. Zbl 1372.68137
Kratsch, Stefan; Sorge, Manuel
2
2015
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1398.68249
Kratsch, Stefan
2
2014
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
2
2018
Point line cover: the easy kernel is essentially tight. Zbl 1423.68548
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
2
2014
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1396.68059
Kratsch, Stefan
2
2018
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1357.68073
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
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
Safe approximation and its relation to kernelization. Zbl 1352.68108
Guo, Jiong; Kanj, Iyad; Kratsch, Stefan
2
2012
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1423.68216
Kratsch, Stefan
2
2012
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
The minimum feasible tileset problem. Zbl 1417.68285
Disser, Yann; Kratsch, Stefan; Sorge, Manuel
1
2015
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
Smaller parameters for vertex cover kernelization. Zbl 1443.68072
Hols, Eva-Maria C.; Kratsch, Stefan
1
2018
A randomized polynomial kernel for subset feedback vertex set. Zbl 1380.68225
Hols, Eva-Maria C.; Kratsch, Stefan
1
2016
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
On polynomial kernels for sparse integer linear programs. Zbl 1354.68127
Kratsch, Stefan
1
2013
Polynomial kernels and user reductions for the workflow satisfiability problem. Zbl 1350.68143
Gutin, Gregory; Kratsch, Stefan; Wahlström, Magnus
1
2016
Parameterized two-player Nash equilibrium. Zbl 1341.05160
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
1
2011
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 07273087
Kratsch, Stefan; Wahlström, Magnus
3
2020
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
6
2018
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
2
2018
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1396.68059
Kratsch, Stefan
2
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
Smaller parameters for vertex cover kernelization. Zbl 1443.68072
Hols, Eva-Maria C.; Kratsch, Stefan
1
2018
Polynomial kernels for weighted problems. Zbl 1353.68122
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
6
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
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 1402.68084
Burton, Benjamin; Cabello, Sergio; Kratsch, Stefan; Pettersson, William
1
2017
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
Point line cover: the easy kernel is essentially tight. Zbl 1423.68547
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
9
2016
A randomized polynomial kernelization for vertex cover with a smaller parameter. Zbl 1397.68103
Kratsch, Stefan
4
2016
On polynomial kernels for sparse integer linear programs. Zbl 1338.68111
Kratsch, Stefan
3
2016
A randomized polynomial kernel for subset feedback vertex set. Zbl 1380.68225
Hols, Eva-Maria C.; Kratsch, Stefan
1
2016
Polynomial kernels and user reductions for the workflow satisfiability problem. Zbl 1350.68143
Gutin, Gregory; Kratsch, Stefan; Wahlström, Magnus
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
40
2015
A completeness theory for polynomial (Turing) kernelization. Zbl 1312.68102
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi
9
2015
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1326.05053
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
7
2015
A structural approach to kernels for ILPs: treewidth and total unimodularity. Zbl 1466.68046
Jansen, Bart M. P.; Kratsch, Stefan
5
2015
A shortcut to (sun)flowers: kernels in logarithmic space or linear time. Zbl 1465.68111
Fafianie, Stefan; Kratsch, Stefan
4
2015
The parameterized complexity of the minimum shared edges problem. Zbl 1366.68090
Fluschnik, Till; Kratsch, Stefan; Niedermeier, Rolf; Sorge, Manuel
4
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
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
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
85
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
17
2014
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
13
2014
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Recent developments in kernelization: a survey. Zbl 1409.68144
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
5
2014
Streaming kernelization. Zbl 1426.68120
Fafianie, Stefan; Kratsch, Stefan
4
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.
3
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
Point line cover: the easy kernel is essentially tight. Zbl 1423.68548
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
2
2014
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2014
Bin packing with fixed number of bins revisited. Zbl 1261.68065
Jansen, Klaus; Kratsch, Stefan; Marx, Dániel; Schlotter, Ildikó
21
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
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1293.05288
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
17
2013
Data reduction for graph coloring problems. Zbl 1435.68124
Jansen, Bart M. P.; Kratsch, Stefan
16
2013
Kernel bounds for path and cycle problems. Zbl 1407.68207
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
11
2013
Preprocessing for treewidth: a combinatorial analysis through kernelization. Zbl 1290.05143
Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
10
2013
Two edge modification problems without polynomial kernels. Zbl 06920189
Kratsch, Stefan; Wahlström, Magnus
10
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
6
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
Parameterized two-player Nash equilibrium. Zbl 1272.68142
Hermelin, Danny; Huang, Chien-Chung; Kratsch, Stefan; Wahlström, Magnus
5
2013
Fixed-parameter evolutionary algorithms and the vertex cover problem. Zbl 1262.68180
Kratsch, Stefan; Neumann, Frank
4
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
2
2013
Fixed-parameter tractability and characterizations of small special treewidth. Zbl 1400.05234
Bodlaender, Hans L.; Kratsch, Stefan; Kreuzen, Vincent J. C.
2
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
On polynomial kernels for sparse integer linear programs. Zbl 1354.68127
Kratsch, Stefan
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
Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP. Zbl 1236.68097
Kratsch, Stefan
4
2012
Fixed-parameter tractability of multicut in directed acyclic graphs. Zbl 1272.68158
Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
4
2012
On polynomial kernels for structural parameterizations of odd cycle transversal. Zbl 1352.68112
Jansen, Bart M. P.; Kratsch, Stefan
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
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1423.68217
Kratsch, Stefan; Wahlström, Magnus
3
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
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Zbl 1423.68216
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
38
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
11
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ó
3
2010
Two edge modification problems without polynomial kernels. Zbl 1273.68181
Kratsch, Stefan; Wahlström, Magnus
21
2009
all top 5

Cited by 474 Authors

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

Cited in 48 Serials

83 Algorithmica
44 Theoretical Computer Science
29 Discrete Applied Mathematics
29 Journal of Computer and System Sciences
24 SIAM Journal on Discrete Mathematics
19 Theory of Computing Systems
13 SIAM Journal on Computing
10 Information Processing Letters
8 Journal of Combinatorial Optimization
7 Information and Computation
5 ACM Transactions on Computation Theory
4 Journal of Scheduling
3 European Journal of Operational Research
3 Discrete Optimization
2 Journal of Combinatorial Theory. Series B
2 Mathematical Programming. Series A. Series B
2 Journal of Graph Algorithms and Applications
2 Computer Science Review
1 Acta Informatica
1 Artificial Intelligence
1 Discrete Mathematics
1 Mathematics of Operations Research
1 European Journal of Combinatorics
1 Operations Research Letters
1 Discrete & Computational Geometry
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 Journal of the ACM
1 Data Mining and Knowledge Discovery
1 RAIRO. Operations Research
1 ACM Journal of Experimental Algorithmics
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