Marek Cygan
TitleCited byYear
Parameterized algorithms
M Cygan, FV Fomin, Ł Kowalik, D Lokshtanov, D Marx, M Pilipczuk, ...
Springer 4 (8), 2015
10432015
Solving connectivity problems parameterized by treewidth in single exponential time
M Cygan, J Nederlof, M Pilipczuk, M Pilipczuk, JMM van Rooij, ...
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 150-159, 2011
2662011
On problems as hard as CNF-SAT
M Cygan, H Dell, D Lokshtanov, D Marx, J Nederlof, Y Okamoto, R Paturi, ...
ACM Transactions on Algorithms (TALG) 12 (3), 41, 2016
1452016
On multiway cut parameterized above lower bounds
M Cygan, M Pilipczuk, M Pilipczuk, JO Wojtaszczyk
International Symposium on Parameterized and Exact Computation, 1-12, 2011
1062011
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
HL Bodlaender, M Cygan, S Kratsch, J Nederlof
Information and Computation 243, 86-111, 2015
862015
Exponential-time approximation of weighted set cover
M Cygan, Ł Kowalik, M Wykurz
Information Processing Letters 109 (16), 957-961, 2009
792009
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
HL Bodlaender, M Cygan, S Kratsch, J Nederlof
International Colloquium on Automata, Languages, and Programming, 196-207, 2013
67*2013
Fast hamiltonicity checking via bases of perfect matchings
M Cygan, S Kratsch, J Nederlof
Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013
612013
LP rounding for k-centers with non-uniform hard capacities
M Cygan, MT Hajiaghayi, S Khuller
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 273-282, 2012
612012
Exact and approximate bandwidth
M Cygan, M Pilipczuk
Theoretical Computer Science 411 (40-42), 3701-3713, 2010
562010
Known algorithms for edge clique cover are probably optimal
M Cygan, M Pilipczuk, M Pilipczuk
SIAM Journal on Computing 45 (1), 67-83, 2016
462016
Improved approximation for 3-dimensional matching via bounded pathwidth local search
M Cygan
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 509-518, 2013
442013
Minimum Bisection is fixed-parameter tractable
M Cygan, D Lokshtanov, M Pilipczuk, M Pilipczuk, S Saurabh
SIAM Journal on Computing 48 (2), 417-450, 2019
432019
Directed subset feedback vertex set is fixed-parameter tractable
R Chitnis, M Cygan, M Hajiaghayi, D Marx
ACM Transactions on Algorithms (TALG) 11 (4), 28, 2015
422015
Clique cover and graph separation: New incompressibility results
M Cygan, S Kratsch, M Pilipczuk, M Pilipczuk, M Wahlström
ACM Transactions on Computation Theory (TOCT) 6 (2), 6, 2014
412014
The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
M Cygan, D Marx, M Pilipczuk, M Pilipczuk
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 197-206, 2013
412013
Subset feedback vertex set is fixed-parameter tractable
M Cygan, M Pilipczuk, M Pilipczuk, JO Wojtaszczyk
SIAM Journal on Discrete Mathematics 27 (1), 290-309, 2013
412013
A fast branching algorithm for cluster vertex deletion
A Boral, M Cygan, T Kociumaka, M Pilipczuk
Theory of Computing Systems 58 (2), 357-376, 2016
39*2016
Designing FPT algorithms for cut problems using randomized contractions
R Chitnis, M Cygan, MT Hajiaghayi, M Pilipczuk, M Pilipczuk
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 460-469, 2012
382012
From gap-eth to fpt-inapproximability: Clique, dominating set, and more
P Chalermsook, M Cygan, G Kortsarz, B Laekhanukit, P Manurangsi, ...
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
362017
The system can't perform the operation now. Try again later.
Articles 1–20