×
Compute Distance To:
Author ID: cygan.marek Recent zbMATH articles by "Cygan, Marek"
Published as: Cygan, Marek; Cygan, M.
all top 5

Co-Authors

1 single-authored
58 Pilipczuk, Marcin L.
46 Pilipczuk, Michał
22 Wojtaszczyk, Jakub Onufry
10 Lokshtanov, Daniel
10 Saurabh, Saket
9 Kowalik, Łukasz
8 Marx, Dániel
8 Sankowski, Piotr
7 Mucha, Marcin
6 Grandoni, Fabrizio
6 Komosa, Paweł
6 Kratsch, Stefan
6 Nederlof, Jesper
5 Bliznets, Ivan A.
5 Fomin, Fedor V.
5 Socała, Arkadiusz
4 Kociumaka, Tomasz
4 Kortsarz, Guy
4 Van Leeuwen, Erik Jan
4 Wahlström, Magnus
3 Chitnis, Rajesh Hemant
3 Kubica, Marcin
3 Mach, Lukáš
3 Radoszewski, Jakub
3 Rytter, Wojciech
3 Waleń, Tomasz
2 Bodlaender, Hans L.
2 Boral, Anudhyan
2 Golovnev, Alexander
2 Hajiaghayi, Mohammad Taghi
2 Heggernes, Pinar
2 Hermelin, Danny
2 Jeż, Łukasz
2 Kulikov, Alexander S.
2 Leonardi, Stefano
2 Lužar, Borut
2 Mihajlin, Ivan
2 Nutov, Zeev
2 Pachocki, Jakub W.
2 Schlotter, Ildikó
2 Škrekovski, Riste
2 Wegrzycki, Karol
2 Włodarczyk, Michał
2 Wrochna, Marcin
1 Bazgan, Cristina
1 Binkele-Raible, Daniel
1 Brach, Paweł
1 Branković, Ljiljana
1 Chalermsook, Parinya
1 Chopin, Morgan
1 Crochemore, Maxime
1 Czumaj, Artur
1 Dell, Holger
1 Englert, Matthias
1 Fellows, Michael Ralph
1 Fernau, Henning
1 Gabow, Harold N.
1 Gupta, Anupam
1 Hajiaghayi, Mohammataghi
1 Halldórsson, Magnús Mar
1 Hou, Jianfeng
1 Iliopoulos, Costas S.
1 Kavitha, Telikepalli
1 Kneis, Joachim
1 Kratsch, Dieter
1 Łącki, Jakub
1 Laekhanukit, Bundit
1 Langer, Alexander
1 Liedloff, Mathieu
1 Manurangsi, Pasin
1 Mastrolilli, Monaldo
1 Nanongkai, Danupon
1 Okamoto, Yoshio
1 Paturi, Ramamohan
1 Philip, Geevarghese
1 Rossmanith, Peter
1 Sgall, Jiří
1 Sornat, Krzysztof
1 Trevisan, Luca
1 van Rooij, Johan M. M.
1 Wu, Jian-Liang
1 Wykurz, Mateusz

Publications by Year

Citations contained in zbMATH Open

94 Publications have been cited 1,225 times in 882 Documents Cited by Year
Parameterized algorithms. Zbl 1334.90001
Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
436
2015
Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). Zbl 1292.68122
Cygan, Marek; Nederlof, Jesper; Pilipczuk, Marcin; Pilipczuk, Michał; van Rooij, Johan M. M.; Wojtaszczyk, Jakub Onufry
123
2011
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1327.68126
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
49
2015
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
31
2013
On problems as hard as CNF-SAT. Zbl 1442.68064
Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus
27
2016
Subset feedback vertex set is fixed-parameter tractable. Zbl 1268.05196
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
25
2013
Exact and approximate bandwidth. Zbl 1207.68443
Cygan, Marek; Pilipczuk, Marcin
24
2010
Minimum bisection is fixed parameter tractable. Zbl 1315.05134
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
21
2014
Designing FPT algorithms for cut problems using randomized contractions. Zbl 1348.68063
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Pilipczuk, Marcin; Pilipczuk, Michał
21
2016
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
Exponential-time approximation of weighted set cover. Zbl 1202.68482
Cygan, Marek; Kowalik, Łukasz; Wykurz, Mateusz
19
2009
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1293.05288
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
18
2013
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
17
2016
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack. Zbl 1225.05227
Binkele-Raible, Daniel; Brankovic, Ljiljana; Cygan, Marek; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Pilipczuk, Marcin; Rossmanith, Peter; Wojtaszczyk, Jakub Onufry
15
2011
On pairwise spanners. Zbl 1354.05131
Cygan, Marek; Grandoni, Fabrizio; Kavitha, Telikepalli
14
2013
Parameterized complexity of Eulerian deletion problems. Zbl 1284.05157
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Schlotter, Ildikó
13
2014
Split Vertex Deletion meets Vertex Cover: new fixed-parameter and exact exponential-time algorithms. Zbl 1259.68256
Cygan, Marek; Pilipczuk, Marcin
13
2013
Directed Subset Feedback Vertex Set is fixed-parameter tractable. Zbl 1272.68149
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Marx, Dániel
13
2012
Deterministic parameterized connected vertex cover. Zbl 1357.05143
Cygan, Marek
13
2012
Subset feedback vertex set is fixed-parameter tractable. Zbl 1334.68096
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
12
2011
A planar linear arboricity conjecture. Zbl 1242.05064
Cygan, Marek; Hou, Jian-Feng; Kowalik, Łukasz; Lužar, Borut; Wu, Jian-Liang
12
2012
On the hardness of losing width. Zbl 1290.68045
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
11
2014
On multiway cut parameterized above lower bounds. Zbl 1352.68100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
11
2012
Known algorithms for edge clique cover are probably optimal. Zbl 1329.05216
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
10
2016
Dominating set is fixed parameter tractable in claw-free graphs. Zbl 1228.68030
Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
9
2011
Kernelization hardness of connectivity problems in \(d\)-degenerate graphs. Zbl 1309.68079
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
9
2010
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
8
2019
Parameterized complexity of firefighting. Zbl 1411.68046
Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan
8
2014
Online knapsack revisited. Zbl 1333.90105
Cygan, Marek; Jeż, Łukasz; Sgall, Jiří
7
2016
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
7
2018
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
6
2014
Capacitated domination faster than \(O(2^{n })\). Zbl 1285.68063
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
6
2010
Algorithmic applications of Baur-Strassen’s theorem, shortest cycles, diameter, and matchings. Zbl 1426.05164
Cygan, Marek; Gabow, Harold N.; Sankowski, Piotr
6
2015
The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem. Zbl 1376.68063
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
6
2011
Even faster exact bandwidth. Zbl 1295.68130
Cygan, Marek; Pilipczuk, Marcin
6
2012
Polynomial kernelization for removing induced claws and diamonds. Zbl 1368.68222
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin
6
2017
Parameterized complexity of Eulerian deletion problems. Zbl 1341.05141
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Schlotter, Ildikó
5
2011
Bandwidth and distortion revisited. Zbl 1236.05196
Cygan, Marek; Pilipczuk, Marcin
5
2012
Faster exact bandwidth. Zbl 1202.05135
Cygan, Marek; Pilipczuk, Marcin
5
2008
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more. Zbl 1452.68083
Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca
5
2020
Scheduling partially ordered jobs faster than \(2^{n }\). Zbl 1346.90336
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
5
2011
Kernelization hardness of connectivity problems in \(d\)-degenerate graphs. Zbl 1252.05100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
5
2012
On cutwidth parameterized by vertex cover. Zbl 1303.05185
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
4
2014
Solving the 2-disjoint connected subgraphs problem faster than \(2^n\). Zbl 1306.05125
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
4
2014
Exact and approximate bandwidth. Zbl 1248.68371
Cygan, Marek; Pilipczuk, Marcin
4
2009
Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. Zbl 1410.68281
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Mach, Lukáš; Pilipczuk, Michał
4
2016
Directed subset feedback vertex set is fixed-parameter tractable. Zbl 1398.68222
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, Mohammataghi; Marx, Dániel
4
2015
How to sell hyperedges: the hypermatching assignment problem. Zbl 1425.90053
Cygan, Marek; Grandoni, Fabrizio; Mastrolilli, Monaldo
4
2013
Polynomial-time approximation algorithms for weighted LCS problem. Zbl 1339.68314
Cygan, Marek; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
4
2011
Relation between Randić index and average distance of trees. Zbl 1265.05140
Cygan, Marek; Pilipczuk, Michał; Škrekovski, Riste.
4
2011
Capacitated domination faster than \(O(2^n)\). Zbl 1260.68494
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
4
2011
An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion. Zbl 1309.68090
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
4
2010
Polynomial kernelization for removing induced claws and diamonds. Zbl 1362.68104
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin
4
2016
Tight kernel bounds for problems on graphs with small degeneracy (extended abstract). Zbl 1394.68173
Cygan, Marek; Grandoni, Fabrizio; Hermelin, Danny
4
2013
On the inequality between radius and Randić index for graphs. Zbl 1289.05060
Cygan, Marek; Pilipczuk, Michał
4
2012
Parameterized complexity of firefighting revisited. Zbl 1352.68098
Cygan, Marek; Fomin, Fedor V.; van Leeuwen, Erik Jan
4
2012
On the hardness of losing width. Zbl 1352.68089
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
4
2012
On group feedback vertex set parameterized by the size of the cutset. Zbl 1331.68100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
4
2012
A fast branching algorithm for cluster vertex deletion. Zbl 1330.68220
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
4
2014
Tight lower bounds on graph embedding problems. Zbl 1426.68099
Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz
4
2017
Faster exponential-time algorithms in graphs of bounded average degree. Zbl 1327.68130
Cygan, Marek; Pilipczuk, Marcin
3
2013
On group feedback vertex set parameterized by the size of the cutset. Zbl 1336.68121
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
3
2016
Algorithmic complexity of power law networks. Zbl 1394.68010
Brach, Paweł; Cygan, Marek; {Łą}cki, Jakub; Sankowski, Piotr
3
2016
Tight bounds for graph homomorphism and subgraph isomorphism. Zbl 1409.68209
Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz
3
2016
Hitting forbidden subgraphs in graphs of bounded treewidth. Zbl 1376.68062
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał
3
2017
Channel assignment via fast zeta transform. Zbl 1260.68170
Cygan, Marek; Kowalik, Łukasz
3
2011
A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more). Zbl 1254.05056
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
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
Steiner forest orientation problems. Zbl 1283.05257
Cygan, Marek; Kortsarz, Guy; Nutov, Zeev
3
2013
On cutwidth parameterized by vertex cover. Zbl 1352.68099
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
3
2012
A path-decomposition theorem with applications to pricing and covering on trees. Zbl 1365.68350
Cygan, Marek; Grandoni, Fabrizio; Leonardi, Stefano; Pilipczuk, Marcin; Sankowski, Piotr
3
2012
Lower bounds for approximation schemes for Closest String. Zbl 1378.68203
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
3
2016
Constant factor approximation for capacitated \(k\)-center with outliers. Zbl 1359.90056
Cygan, Marek; Kociumaka, Tomasz
2
2014
Scheduling partially ordered jobs faster than \(2^n\). Zbl 1360.90124
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2014
Faster exponential-time algorithms in graphs of bounded average degree. Zbl 1334.68095
Cygan, Marek; Pilipczuk, Marcin
2
2015
Algorithms for three versions of the shortest common superstring problem. Zbl 1286.68523
Crochemore, Maxime; Cygan, Marek; Iliopoulos, Costas; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
2
2010
A planar linear arboricity conjecture. Zbl 1284.05211
Cygan, Marek; Kowalik, Łukasz; Lužar, Borut
2
2010
Irredundant set faster than \(O(2^{n })\). Zbl 1284.05279
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
2
2010
Polynomial-time approximation algorithms for weighted LCS problem. Zbl 1335.68304
Cygan, M.; Kubica, M.; Radoszewski, J.; Rytter, W.; Waleń, T.
2
2016
Approximation and parameterized complexity of minimax approval voting. Zbl 1451.68130
Cygan, Marek; Kowalik, Łukasz; Socała, Arkadiusz; Sornat, Krzysztof
2
2018
Improving TSP tours using dynamic programming over tree decompositions. Zbl 1442.68286
Cygan, Marek; Kowalik, Łukasz; Socała, Arkadiusz
2
2017
Minimum bisection is fixed-parameter tractable. Zbl 1421.68069
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
2
2019
Known algorithms for edge clique cover are probably optimal. Zbl 1423.05130
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal
2
2013
An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Zbl 1252.68150
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2012
Sitting closer to friends than enemies, revisited. Zbl 1365.68351
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2012
Steiner forest orientation problems. Zbl 1365.68276
Cygan, Marek; Kortsarz, Guy; Nutov, Zeev
2
2012
Sitting closer to friends than enemies, revisited. Zbl 1312.05067
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
1
2015
Online knapsack revisited. Zbl 1417.90126
Cygan, Marek; Jeż, Łukasz
1
2014
On problems equivalent to \((\min,+)\)-convolution. Zbl 1441.68070
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
1
2017
Hardness of approximation for \(H\)-free edge modification problems. Zbl 1427.68105
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał
1
2018
A bound on the number of perfect matchings in Klee-graphs. Zbl 1283.05212
Cygan, Marek; Pilipczuk, Marcin; Škrekovski, Riste
1
2013
Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\). Zbl 1353.68117
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
1
2012
Approximation algorithms for union and intersection covering problems. Zbl 1246.68262
Cygan, Marek; Grandoni, Fabrizio; Leonardi, Stefano; Mucha, Marcin; Pilipczuk, Marcin; Sankowski, Piotr
1
2011
Hardness of approximation for \(H\)-free edge modification problems. Zbl 1398.68188
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał
1
2016
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more. Zbl 1452.68083
Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca
5
2020
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
8
2019
Minimum bisection is fixed-parameter tractable. Zbl 1421.68069
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
2
2019
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
7
2018
Approximation and parameterized complexity of minimax approval voting. Zbl 1451.68130
Cygan, Marek; Kowalik, Łukasz; Socała, Arkadiusz; Sornat, Krzysztof
2
2018
Hardness of approximation for \(H\)-free edge modification problems. Zbl 1427.68105
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał
1
2018
Polynomial kernelization for removing induced claws and diamonds. Zbl 1368.68222
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin
6
2017
Tight lower bounds on graph embedding problems. Zbl 1426.68099
Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz
4
2017
Hitting forbidden subgraphs in graphs of bounded treewidth. Zbl 1376.68062
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał
3
2017
Improving TSP tours using dynamic programming over tree decompositions. Zbl 1442.68286
Cygan, Marek; Kowalik, Łukasz; Socała, Arkadiusz
2
2017
On problems equivalent to \((\min,+)\)-convolution. Zbl 1441.68070
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
1
2017
On problems as hard as CNF-SAT. Zbl 1442.68064
Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus
27
2016
Designing FPT algorithms for cut problems using randomized contractions. Zbl 1348.68063
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Pilipczuk, Marcin; Pilipczuk, Michał
21
2016
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
17
2016
Known algorithms for edge clique cover are probably optimal. Zbl 1329.05216
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
10
2016
Online knapsack revisited. Zbl 1333.90105
Cygan, Marek; Jeż, Łukasz; Sgall, Jiří
7
2016
Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. Zbl 1410.68281
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Mach, Lukáš; Pilipczuk, Michał
4
2016
Polynomial kernelization for removing induced claws and diamonds. Zbl 1362.68104
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin
4
2016
On group feedback vertex set parameterized by the size of the cutset. Zbl 1336.68121
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
3
2016
Algorithmic complexity of power law networks. Zbl 1394.68010
Brach, Paweł; Cygan, Marek; {Łą}cki, Jakub; Sankowski, Piotr
3
2016
Tight bounds for graph homomorphism and subgraph isomorphism. Zbl 1409.68209
Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz
3
2016
Lower bounds for approximation schemes for Closest String. Zbl 1378.68203
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
3
2016
Polynomial-time approximation algorithms for weighted LCS problem. Zbl 1335.68304
Cygan, M.; Kubica, M.; Radoszewski, J.; Rytter, W.; Waleń, T.
2
2016
Hardness of approximation for \(H\)-free edge modification problems. Zbl 1398.68188
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał
1
2016
Parameterized algorithms. Zbl 1334.90001
Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
436
2015
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Zbl 1327.68126
Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
49
2015
Algorithmic applications of Baur-Strassen’s theorem, shortest cycles, diameter, and matchings. Zbl 1426.05164
Cygan, Marek; Gabow, Harold N.; Sankowski, Piotr
6
2015
Directed subset feedback vertex set is fixed-parameter tractable. Zbl 1398.68222
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, Mohammataghi; Marx, Dániel
4
2015
Faster exponential-time algorithms in graphs of bounded average degree. Zbl 1334.68095
Cygan, Marek; Pilipczuk, Marcin
2
2015
Sitting closer to friends than enemies, revisited. Zbl 1312.05067
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
1
2015
Minimum bisection is fixed parameter tractable. Zbl 1315.05134
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
21
2014
Parameterized complexity of Eulerian deletion problems. Zbl 1284.05157
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Schlotter, Ildikó
13
2014
On the hardness of losing width. Zbl 1290.68045
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
11
2014
Parameterized complexity of firefighting. Zbl 1411.68046
Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan
8
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
On cutwidth parameterized by vertex cover. Zbl 1303.05185
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
4
2014
Solving the 2-disjoint connected subgraphs problem faster than \(2^n\). Zbl 1306.05125
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
4
2014
A fast branching algorithm for cluster vertex deletion. Zbl 1330.68220
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
4
2014
Constant factor approximation for capacitated \(k\)-center with outliers. Zbl 1359.90056
Cygan, Marek; Kociumaka, Tomasz
2
2014
Scheduling partially ordered jobs faster than \(2^n\). Zbl 1360.90124
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2014
Online knapsack revisited. Zbl 1417.90126
Cygan, Marek; Jeż, Łukasz
1
2014
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
31
2013
Subset feedback vertex set is fixed-parameter tractable. Zbl 1268.05196
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
25
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
18
2013
On pairwise spanners. Zbl 1354.05131
Cygan, Marek; Grandoni, Fabrizio; Kavitha, Telikepalli
14
2013
Split Vertex Deletion meets Vertex Cover: new fixed-parameter and exact exponential-time algorithms. Zbl 1259.68256
Cygan, Marek; Pilipczuk, Marcin
13
2013
How to sell hyperedges: the hypermatching assignment problem. Zbl 1425.90053
Cygan, Marek; Grandoni, Fabrizio; Mastrolilli, Monaldo
4
2013
Tight kernel bounds for problems on graphs with small degeneracy (extended abstract). Zbl 1394.68173
Cygan, Marek; Grandoni, Fabrizio; Hermelin, Danny
4
2013
Faster exponential-time algorithms in graphs of bounded average degree. Zbl 1327.68130
Cygan, Marek; Pilipczuk, Marcin
3
2013
Steiner forest orientation problems. Zbl 1283.05257
Cygan, Marek; Kortsarz, Guy; Nutov, Zeev
3
2013
Known algorithms for edge clique cover are probably optimal. Zbl 1423.05130
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal
2
2013
A bound on the number of perfect matchings in Klee-graphs. Zbl 1283.05212
Cygan, Marek; Pilipczuk, Marcin; Škrekovski, Riste
1
2013
Directed Subset Feedback Vertex Set is fixed-parameter tractable. Zbl 1272.68149
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, MohammadTaghi; Marx, Dániel
13
2012
Deterministic parameterized connected vertex cover. Zbl 1357.05143
Cygan, Marek
13
2012
A planar linear arboricity conjecture. Zbl 1242.05064
Cygan, Marek; Hou, Jian-Feng; Kowalik, Łukasz; Lužar, Borut; Wu, Jian-Liang
12
2012
On multiway cut parameterized above lower bounds. Zbl 1352.68100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
11
2012
Even faster exact bandwidth. Zbl 1295.68130
Cygan, Marek; Pilipczuk, Marcin
6
2012
Bandwidth and distortion revisited. Zbl 1236.05196
Cygan, Marek; Pilipczuk, Marcin
5
2012
Kernelization hardness of connectivity problems in \(d\)-degenerate graphs. Zbl 1252.05100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
5
2012
On the inequality between radius and Randić index for graphs. Zbl 1289.05060
Cygan, Marek; Pilipczuk, Michał
4
2012
Parameterized complexity of firefighting revisited. Zbl 1352.68098
Cygan, Marek; Fomin, Fedor V.; van Leeuwen, Erik Jan
4
2012
On the hardness of losing width. Zbl 1352.68089
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
4
2012
On group feedback vertex set parameterized by the size of the cutset. Zbl 1331.68100
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał
4
2012
A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more). Zbl 1254.05056
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
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 cutwidth parameterized by vertex cover. Zbl 1352.68099
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
3
2012
A path-decomposition theorem with applications to pricing and covering on trees. Zbl 1365.68350
Cygan, Marek; Grandoni, Fabrizio; Leonardi, Stefano; Pilipczuk, Marcin; Sankowski, Piotr
3
2012
An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Zbl 1252.68150
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2012
Sitting closer to friends than enemies, revisited. Zbl 1365.68351
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
2
2012
Steiner forest orientation problems. Zbl 1365.68276
Cygan, Marek; Kortsarz, Guy; Nutov, Zeev
2
2012
Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\). Zbl 1353.68117
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
1
2012
Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). Zbl 1292.68122
Cygan, Marek; Nederlof, Jesper; Pilipczuk, Marcin; Pilipczuk, Michał; van Rooij, Johan M. M.; Wojtaszczyk, Jakub Onufry
123
2011
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack. Zbl 1225.05227
Binkele-Raible, Daniel; Brankovic, Ljiljana; Cygan, Marek; Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Pilipczuk, Marcin; Rossmanith, Peter; Wojtaszczyk, Jakub Onufry
15
2011
Subset feedback vertex set is fixed-parameter tractable. Zbl 1334.68096
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
12
2011
Dominating set is fixed parameter tractable in claw-free graphs. Zbl 1228.68030
Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
9
2011
The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem. Zbl 1376.68063
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
6
2011
Parameterized complexity of Eulerian deletion problems. Zbl 1341.05141
Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Schlotter, Ildikó
5
2011
Scheduling partially ordered jobs faster than \(2^{n }\). Zbl 1346.90336
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
5
2011
Polynomial-time approximation algorithms for weighted LCS problem. Zbl 1339.68314
Cygan, Marek; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
4
2011
Relation between Randić index and average distance of trees. Zbl 1265.05140
Cygan, Marek; Pilipczuk, Michał; Škrekovski, Riste.
4
2011
Capacitated domination faster than \(O(2^n)\). Zbl 1260.68494
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
4
2011
Channel assignment via fast zeta transform. Zbl 1260.68170
Cygan, Marek; Kowalik, Łukasz
3
2011
Approximation algorithms for union and intersection covering problems. Zbl 1246.68262
Cygan, Marek; Grandoni, Fabrizio; Leonardi, Stefano; Mucha, Marcin; Pilipczuk, Marcin; Sankowski, Piotr
1
2011
Exact and approximate bandwidth. Zbl 1207.68443
Cygan, Marek; Pilipczuk, Marcin
24
2010
Kernelization hardness of connectivity problems in \(d\)-degenerate graphs. Zbl 1309.68079
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
9
2010
Capacitated domination faster than \(O(2^{n })\). Zbl 1285.68063
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
6
2010
An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion. Zbl 1309.68090
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
4
2010
Algorithms for three versions of the shortest common superstring problem. Zbl 1286.68523
Crochemore, Maxime; Cygan, Marek; Iliopoulos, Costas; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
2
2010
A planar linear arboricity conjecture. Zbl 1284.05211
Cygan, Marek; Kowalik, Łukasz; Lužar, Borut
2
2010
Irredundant set faster than \(O(2^{n })\). Zbl 1284.05279
Cygan, Marek; Pilipczuk, Marcin; Wojtaszczyk, Jakub Onufry
2
2010
Exponential-time approximation of weighted set cover. Zbl 1202.68482
Cygan, Marek; Kowalik, Łukasz; Wykurz, Mateusz
19
2009
Exact and approximate bandwidth. Zbl 1248.68371
Cygan, Marek; Pilipczuk, Marcin
4
2009
Faster exact bandwidth. Zbl 1202.05135
Cygan, Marek; Pilipczuk, Marcin
5
2008
all top 5

Cited by 1,048 Authors

72 Saurabh, Saket
39 Fomin, Fedor V.
34 Golovach, Petr A.
34 Lokshtanov, Daniel
33 Pilipczuk, Marcin L.
32 Sau, Ignasi
30 Pilipczuk, Michał
30 Zehavi, Meirav
23 Cygan, Marek
22 Jansen, Bart M. P.
22 Niedermeier, Rolf
21 Raman, Venkatesh
21 Thilikos, Dimitrios M.
20 Ramanujan, M. S.
19 Bodlaender, Hans L.
19 Marx, Dániel
19 Panolan, Fahad
19 Paschos, Vangelis Th.
19 Van Leeuwen, Erik Jan
18 Gutin, Gregory Z.
18 Kratsch, Stefan
18 Wang, Jianxin
17 Fernau, Henning
17 Komusiewicz, Christian
16 Lampis, Michael
16 Sorge, Manuel
16 van Bevern, René
15 Agrawal, Akanksha
15 Baste, Julien
15 Ganian, Robert
15 Misra, Neeldhara
15 Otachi, Yota
15 Philip, Geevarghese
14 Bonnet, Edouard
14 Kratsch, Dieter
14 Liedloff, Mathieu
14 Ordyniak, Sebastian
14 Paulusma, Daniël
13 Eiben, Eduard
13 Hermelin, Danny
13 Tale, Prafullkumar
12 Feng, Qilong
12 Hanaka, Tesshu
12 Molter, Hendrik
12 Paul, Christophe
12 Wahlström, Magnus
11 Heggernes, Pinar
11 Kowalik, Łukasz
11 Kwon, Ojoung
11 Suchý, Ondřej
10 Fluschnik, Till
10 Kolay, Sudeshna
10 Krithika, R.
10 Mnich, Matthias
9 Bredereck, Robert
9 Escoffier, Bruno
9 Knop, Dušan
9 Majumdar, Diptapriyo
9 Ono, Hirotaka
9 Wojtaszczyk, Jakub Onufry
8 Casel, Katrin
8 Feldmann, Andreas Emil
8 Kobayashi, Yusuke
8 Li, Shaohua
8 Mertzios, George B.
8 Mouawad, Amer E.
8 Nichterlein, André
8 Rzążewski, Paweł
7 Bazgan, Cristina
7 Bergougnoux, Benjamin
7 Cao, Yixin
7 Chen, Jian-er
7 Chitnis, Rajesh Hemant
7 Gupta, Sushmita
7 Lima, Paloma T.
7 Reidl, Felix
7 Sikora, Florian
7 van der Zanden, Tom C.
7 Yeo, Anders
6 Belmonte, Rémy
6 Björklund, Andreas
6 Jaffke, Lars
6 Kim, Eunjung
6 Kisfaludi-Bak, Sándor
6 Kiyomi, Masashi
6 Kobayashi, Yasuaki
6 Lauri, Juho
6 Misra, Pranabendu
6 Nederlof, Jesper
6 Papadopoulos, Charis
6 Rai, Ashutosh
6 Shachnai, Hadas
6 Xiao, Mingyu
5 Araújo, Júlio César Silva
5 Bousquet, Nicolas
5 Branković, Ljiljana
5 Chen, Jiehua
5 Faliszewski, Piotr
5 Faria, Luerbio
5 Froese, Vincent
...and 948 more Authors
all top 5

Cited in 76 Serials

135 Algorithmica
132 Theoretical Computer Science
60 Journal of Computer and System Sciences
56 Discrete Applied Mathematics
46 SIAM Journal on Discrete Mathematics
34 Information Processing Letters
32 Theory of Computing Systems
23 SIAM Journal on Computing
18 Journal of Combinatorial Optimization
14 Information and Computation
10 Artificial Intelligence
10 Discrete Mathematics
9 Journal of Discrete Algorithms
7 Journal of Graph Algorithms and Applications
6 European Journal of Combinatorics
5 Mathematical Programming. Series A. Series B
5 Journal of Scheduling
5 Optimization Letters
4 Annals of Operations Research
4 Discrete Optimization
4 Computer Science Review
3 Applied Mathematics and Computation
3 Discrete & Computational Geometry
3 Computers & Operations Research
3 International Journal of Foundations of Computer Science
3 European Journal of Operational Research
3 Distributed Computing
3 The Electronic Journal of Combinatorics
2 Journal of Combinatorial Theory. Series B
2 Operations Research
2 Operations Research Letters
2 Combinatorica
2 Computational Geometry
2 RAIRO. Operations Research
2 Algorithms
2 Journal of the Operations Research Society of China
1 Acta Informatica
1 Rocky Mountain Journal of Mathematics
1 Bulletin of Mathematical Biology
1 Information Sciences
1 Mathematics of Operations Research
1 Networks
1 Moscow University Computational Mathematics and Cybernetics
1 Advances in Applied Mathematics
1 Mathematical Social Sciences
1 Social Choice and Welfare
1 Acta Mathematicae Applicatae Sinica. English Series
1 Optimization
1 Journal of Automated Reasoning
1 Journal of Global Optimization
1 Historia Mathematica
1 Computational Complexity
1 International Journal of Computer Vision
1 The Journal of Artificial Intelligence Research (JAIR)
1 Annals of Mathematics and Artificial Intelligence
1 Discussiones Mathematicae. Graph Theory
1 CEJOR. Central European Journal of Operations Research
1 Fundamenta Informaticae
1 Central European Journal of Mathematics
1 Quantum Information Processing
1 4OR
1 Internet Mathematics
1 Sibirskie Èlektronnye Matematicheskie Izvestiya
1 Proceedings of the Steklov Institute of Mathematics
1 Mathematics in Computer Science
1 Logical Methods in Computer Science
1 Asian-European Journal of Mathematics
1 Discrete Mathematics, Algorithms and Applications
1 Mathematical Programming Computation
1 Science China. Information Sciences
1 RAIRO. Theoretical Informatics and Applications
1 ACM Transactions on Algorithms
1 ACM Transactions on Computation Theory
1 Bulletin of the Hellenic Mathematical Society
1 AIMS Mathematics
1 Prikladnaya Diskretnaya Matematika

Citations by Year