Marek Cygan
Marek Cygan
Preverjeni e-poštni naslov na mimuw.edu.pl
Naslov
Navedeno
Navedeno
Leto
Parameterized algorithms
M Cygan, FV Fomin, Ł Kowalik, D Lokshtanov, D Marx, M Pilipczuk, ...
Springer 5 (4), 16, 2015
17592015
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
3272011
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), 1-24, 2016
1892016
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
1522015
On multiway cut parameterized above lower bounds
M Cygan, M Pilipczuk, M Pilipczuk, JO Wojtaszczyk
ACM Transactions on Computation Theory (TOCT) 5 (1), 1-11, 2013
1262013
Exponential-time approximation of weighted set cover
M Cygan, Ł Kowalik, M Wykurz
Information Processing Letters 109 (16), 957-961, 2009
942009
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
772017
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
742012
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
69*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
672013
Known algorithms for edge clique cover are probably optimal
M Cygan, M Pilipczuk, M Pilipczuk
SIAM Journal on Computing 45 (1), 67-83, 2016
652016
Directed subset feedback vertex set is fixed-parameter tractable
R Chitnis, M Cygan, M Hajiaghayi, D Marx
ACM Transactions on Algorithms (TALG) 11 (4), 1-28, 2015
632015
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
612013
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
592013
Exact and approximate bandwidth
M Cygan, M Pilipczuk
Theoretical Computer Science 411 (40-42), 3701-3713, 2010
592010
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
582019
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
582013
Algorithmic applications of Baur-Strassen’s theorem: Shortest cycles, diameter, and matchings
M Cygan, HN Gabow, P Sankowski
Journal of the ACM (JACM) 62 (4), 1-30, 2015
532015
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), 1-19, 2014
512014
Designing FPT algorithms for cut problems using randomized contractions
R Chitnis, M Cygan, MT Hajiaghayi, M Pilipczuk, M Pilipczuk
SIAM Journal on Computing 45 (4), 1171-1229, 2016
492016
Sistem trenutno ne more izvesti postopka. Poskusite znova pozneje.
Članki 1–20