DBLP: Marek Cygan

	2013
j15		Marek Cygan, Marcin Pilipczuk, Riste Skrekovski: A bound on the number of perfect matchings in Klee-graphs. Discrete Mathematics & Theoretical Computer Science 15(1): 37-54 (2013)
j14		Marek Cygan, Marcin Pilipczuk: Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5-6): 179-182 (2013)
j13		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. SIAM J. Discrete Math. 27(1): 290-309 (2013)
c36		Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski: Catch them if you can: how to serve impatient users. ITCS 2013: 485-494
c35		Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli: How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013: 342-351
c34		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA 2013: 1044-1053
c33		Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha: On Pairwise Spanners. STACS 2013: 209-220
i32		Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha: On Pairwise Spanners. CoRR abs/1301.1999 (2013)
i31		Marek Cygan, Marcin Pilipczuk: Faster exponential-time algorithms in graphs of bounded average degree. CoRR abs/1302.3763 (2013)
i30		Marek Cygan: Improved approximation for 3-dimensional matching via bounded pathwidth local search. CoRR abs/1304.1424 (2013)
i29		Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk: The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable. CoRR abs/1304.4207 (2013)
	2012
j12		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion. Algorithmica 64(1): 170-188 (2012)
j11		Marek Cygan, Marcin Pilipczuk: Bandwidth and distortion revisited. Discrete Applied Mathematics 160(4-5): 494-504 (2012)
j10		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Applied Mathematics 160(15): 2131-2141 (2012)
j9		Marek Cygan, Jian-Feng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang Wu: A Planar linear arboricity conjecture. Journal of Graph Theory 69(4): 403-425 (2012)
j8		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). SIAM J. Comput. 41(4): 815-828 (2012)
j7		Marek Cygan, Marcin Pilipczuk: Even Faster Exact Bandwidth. ACM Transactions on Algorithms 8(1): 8 (2012)
c32		Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström: On Problems as Hard as CNF-SAT. IEEE Conference on Computational Complexity 2012: 74-84
c31		Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski: A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. ESA 2012: 349-360
c30		Marek Cygan, Guy Kortsarz, Zeev Nutov: Steiner Forest Orientation Problems. ESA 2012: 361-372
c29		Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller: LP Rounding for k-Centers with Non-uniform Hard Capacities. FOCS 2012: 273-282
c28		Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk: Designing FPT Algorithms for Cut Problems Using Randomized Contractions. FOCS 2012: 460-469
c27		Marek Cygan, Harold N. Gabow, Piotr Sankowski: Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. FOCS 2012: 531-540
c26		Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2012: 230-241
c25		Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström: Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) 2012: 254-265
c24		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n. LATIN 2012: 195-206
c23		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Sitting Closer to Friends Than Enemies, Revisited. MFCS 2012: 296-307
c22		Marek Cygan: Deterministic Parameterized Connected Vertex Cover. SWAT 2012: 95-106
c21		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: On Group Feedback Vertex Set Parameterized by the Size of the Cutset. WG 2012: 194-205
i28		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Sitting closer to friends than enemies, revisited. CoRR abs/1201.1869 (2012)
i27		Marek Cygan: Deterministic parameterized connected vertex cover. CoRR abs/1202.6642 (2012)
i26		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: Known algorithms for EDGE CLIQUE COVER are probably optimal. CoRR abs/1203.1754 (2012)
i25		Marek Cygan, Harold N. Gabow, Piotr Sankowski: Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. CoRR abs/1204.1616 (2012)
i24		Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. CoRR abs/1205.1271 (2012)
i23		Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk: Designing FPT algorithms for cut problems using randomized contractions. CoRR abs/1207.4079 (2012)
i22		Marek Cygan, Marcin Pilipczuk: On fixed-parameter algorithms for Split Vertex Deletion. CoRR abs/1208.1248 (2012)
i21		Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller: LP Rounding for k-Centers with Non-uniform Hard Capacities. CoRR abs/1208.3054 (2012)
i20		Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof: Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR abs/1211.1505 (2012)
i19		Marek Cygan, Stefan Kratsch, Jesper Nederlof: Fast Hamiltonicity checking via bases of perfect matchings. CoRR abs/1211.1506 (2012)
	2011
j6		Marek Cygan, Lukasz Kowalik: Channel assignment via fast zeta transform. Inf. Process. Lett. 111(15): 727-730 (2011)
j5		Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Capacitated domination faster than O(n²). Inf. Process. Lett. 111(23-24): 1099-1103 (2011)
j4		Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk: Breaking the 2ⁿ-barrier for Irredundance: Two lines of attack. J. Discrete Algorithms 9(3): 214-230 (2011)
j3		Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50): 6982-7000 (2011)
c20		Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen: Polynomial-Time Approximation Algorithms for Weighted LCS Problem. CPM 2011: 455-466
c19		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Scheduling Partially Ordered Jobs Faster Than 2 n. ESA 2011: 299-310
c18		Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. FOCS 2011: 150-159
c17		Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Approximation Algorithms for Union and Intersection Covering Problems. FSTTCS 2011: 28-40
c16		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2011: 449-461
c15		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: On Multiway Cut Parameterized above Lower Bounds. IPEC 2011: 1-12
c14		Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized Complexity of Firefighting Revisited. IPEC 2011: 13-26
c13		Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: On the Hardness of Losing Width. IPEC 2011: 159-168
c12		Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: On Cutwidth Parameterized by Vertex Cover. IPEC 2011: 246-258
c11		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). SODA 2011: 1666-1674
c10		Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter: Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142
i18		Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Approximation Algorithms for Union and Intersection Covering Problems. CoRR abs/1102.5105 (2011)
i17		Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR abs/1103.0534 (2011)
i16		Marek Cygan, Lukasz Kowalik: Channel Assignment via Fast Zeta Transform. CoRR abs/1103.2275 (2011)
i15		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: On Multiway Cut parameterized above lower bounds. CoRR abs/1107.1585 (2011)
i14		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Scheduling partially ordered jobs faster than 2^n. CoRR abs/1108.0810 (2011)
i13		Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized Complexity of Firefighting Revisited. CoRR abs/1109.4729 (2011)
i12		Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström: Clique cover and graph separation: New incompressibility results. CoRR abs/1111.0570 (2011)
i11		Marek Cygan, Guy Kortsarz, Zeev Nutov: Steiner Forest Orientation Problems. CoRR abs/1112.2273 (2011)
i10		Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström: On Problems as Hard as CNFSAT. CoRR abs/1112.2275 (2011)
i9		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: On group feedback vertex set parameterized by the size of the cutset. CoRR abs/1112.6255 (2011)
	2010
j2		Marek Cygan, Marcin Pilipczuk: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42): 3701-3713 (2010)
c9		Marek Cygan, Lukasz Kowalik, Borut Luzar: A Planar Linear Arboricity Conjecture. CIAC 2010: 204-216
c8		Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Irredundant Set Faster Than O(2ⁿ). CIAC 2010: 288-298
c7		Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen: Algorithms for Three Versions of the Shortest Common Superstring Problem. CPM 2010: 299-309
c6		Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Fast Approximation in Subspaces by Doubling Metric Decomposition. ESA (1) 2010: 72-83
c5		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion. IPEC 2010: 95-106
c4		Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Capacitated Domination Faster Than O(2ⁿ). SWAT 2010: 74-80
c3		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. WG 2010: 147-158
i8		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset feedback vertex set is fixed parameter tractable. CoRR abs/1004.2972 (2010)
i7		Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). CoRR abs/1004.5010 (2010)
i6		Marek Cygan, Marcin Pilipczuk: Bandwidth and Distortion Revisited. CoRR abs/1004.5012 (2010)
i5		Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Dominating Set is Fixed Parameter Tractable in Claw-free Graphs. CoRR abs/1011.6239 (2010)
	2009
j1		Marek Cygan, Lukasz Kowalik, Mateusz Wykurz: Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16): 957-961 (2009)
c2		Marek Cygan, Marcin Pilipczuk: Exact and Approximate Bandwidth. ICALP (1) 2009: 304-315
i4		Marek Cygan, Marcin Pilipczuk: Even Faster Exact Bandwidth. CoRR abs/0902.1661 (2009)
i3		Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Beyond O*(2^n) in domination-type problems. CoRR abs/0909.4021 (2009)
i2		Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Fast Approximation in Subspaces by Doubling Metric Decomposition. CoRR abs/0911.1626 (2009)
	2008
c1		Marek Cygan, Marcin Pilipczuk: Faster Exact Bandwidth. WG 2008: 101-109
i1		Marek Cygan, Lukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz: Exponential-Time Approximation of Hard Problems. CoRR abs/0810.4934 (2008)

2013

j15

Marek Cygan, Marcin Pilipczuk, Riste Skrekovski: A bound on the number of perfect matchings in Klee-graphs. Discrete Mathematics & Theoretical Computer Science 15(1): 37-54 (2013)

j14

Marek Cygan, Marcin Pilipczuk: Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5-6): 179-182 (2013)

j13

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. SIAM J. Discrete Math. 27(1): 290-309 (2013)

c36

Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski: Catch them if you can: how to serve impatient users. ITCS 2013: 485-494

c35

Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli: How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013: 342-351

c34

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA 2013: 1044-1053

c33

Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha: On Pairwise Spanners. STACS 2013: 209-220

i32

Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha: On Pairwise Spanners. CoRR abs/1301.1999 (2013)

i31

Marek Cygan, Marcin Pilipczuk: Faster exponential-time algorithms in graphs of bounded average degree. CoRR abs/1302.3763 (2013)

i30

Marek Cygan: Improved approximation for 3-dimensional matching via bounded pathwidth local search. CoRR abs/1304.1424 (2013)

i29

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk: The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable. CoRR abs/1304.4207 (2013)

2012

j12

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion. Algorithmica 64(1): 170-188 (2012)

j11

Marek Cygan, Marcin Pilipczuk: Bandwidth and distortion revisited. Discrete Applied Mathematics 160(4-5): 494-504 (2012)

j10

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Applied Mathematics 160(15): 2131-2141 (2012)

Marek Cygan, Jian-Feng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang Wu: A Planar linear arboricity conjecture. Journal of Graph Theory 69(4): 403-425 (2012)

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). SIAM J. Comput. 41(4): 815-828 (2012)

Marek Cygan, Marcin Pilipczuk: Even Faster Exact Bandwidth. ACM Transactions on Algorithms 8(1): 8 (2012)

c32

Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström: On Problems as Hard as CNF-SAT. IEEE Conference on Computational Complexity 2012: 74-84

c31

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski: A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. ESA 2012: 349-360

c30

Marek Cygan, Guy Kortsarz, Zeev Nutov: Steiner Forest Orientation Problems. ESA 2012: 361-372

c29

Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller: LP Rounding for k-Centers with Non-uniform Hard Capacities. FOCS 2012: 273-282

c28

Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk: Designing FPT Algorithms for Cut Problems Using Randomized Contractions. FOCS 2012: 460-469

c27

Marek Cygan, Harold N. Gabow, Piotr Sankowski: Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. FOCS 2012: 531-540

c26

Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2012: 230-241

c25

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström: Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) 2012: 254-265

c24

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n. LATIN 2012: 195-206

c23

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Sitting Closer to Friends Than Enemies, Revisited. MFCS 2012: 296-307

c22

Marek Cygan: Deterministic Parameterized Connected Vertex Cover. SWAT 2012: 95-106

c21

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: On Group Feedback Vertex Set Parameterized by the Size of the Cutset. WG 2012: 194-205

i28

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Sitting closer to friends than enemies, revisited. CoRR abs/1201.1869 (2012)

i27

Marek Cygan: Deterministic parameterized connected vertex cover. CoRR abs/1202.6642 (2012)

i26

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: Known algorithms for EDGE CLIQUE COVER are probably optimal. CoRR abs/1203.1754 (2012)

i25

Marek Cygan, Harold N. Gabow, Piotr Sankowski: Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. CoRR abs/1204.1616 (2012)

i24

Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. CoRR abs/1205.1271 (2012)

i23

Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk: Designing FPT algorithms for cut problems using randomized contractions. CoRR abs/1207.4079 (2012)

i22

Marek Cygan, Marcin Pilipczuk: On fixed-parameter algorithms for Split Vertex Deletion. CoRR abs/1208.1248 (2012)

i21

Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller: LP Rounding for k-Centers with Non-uniform Hard Capacities. CoRR abs/1208.3054 (2012)

i20

Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof: Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR abs/1211.1505 (2012)

i19

Marek Cygan, Stefan Kratsch, Jesper Nederlof: Fast Hamiltonicity checking via bases of perfect matchings. CoRR abs/1211.1506 (2012)

2011

Marek Cygan, Lukasz Kowalik: Channel assignment via fast zeta transform. Inf. Process. Lett. 111(15): 727-730 (2011)

Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Capacitated domination faster than O(n²). Inf. Process. Lett. 111(23-24): 1099-1103 (2011)

Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk: Breaking the 2ⁿ-barrier for Irredundance: Two lines of attack. J. Discrete Algorithms 9(3): 214-230 (2011)

Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50): 6982-7000 (2011)

c20

Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen: Polynomial-Time Approximation Algorithms for Weighted LCS Problem. CPM 2011: 455-466

c19

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Scheduling Partially Ordered Jobs Faster Than 2 n. ESA 2011: 299-310

c18

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. FOCS 2011: 150-159

c17

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Approximation Algorithms for Union and Intersection Covering Problems. FSTTCS 2011: 28-40

c16

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2011: 449-461

c15

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: On Multiway Cut Parameterized above Lower Bounds. IPEC 2011: 1-12

c14

Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized Complexity of Firefighting Revisited. IPEC 2011: 13-26

c13

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: On the Hardness of Losing Width. IPEC 2011: 159-168

c12

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: On Cutwidth Parameterized by Vertex Cover. IPEC 2011: 246-258

c11

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). SODA 2011: 1666-1674

c10

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter: Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142

i18

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Approximation Algorithms for Union and Intersection Covering Problems. CoRR abs/1102.5105 (2011)

i17

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR abs/1103.0534 (2011)

i16

Marek Cygan, Lukasz Kowalik: Channel Assignment via Fast Zeta Transform. CoRR abs/1103.2275 (2011)

i15

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: On Multiway Cut parameterized above lower bounds. CoRR abs/1107.1585 (2011)

i14

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Scheduling partially ordered jobs faster than 2^n. CoRR abs/1108.0810 (2011)

i13

Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized Complexity of Firefighting Revisited. CoRR abs/1109.4729 (2011)

i12

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström: Clique cover and graph separation: New incompressibility results. CoRR abs/1111.0570 (2011)

i11

Marek Cygan, Guy Kortsarz, Zeev Nutov: Steiner Forest Orientation Problems. CoRR abs/1112.2273 (2011)

i10

Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström: On Problems as Hard as CNFSAT. CoRR abs/1112.2275 (2011)

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk: On group feedback vertex set parameterized by the size of the cutset. CoRR abs/1112.6255 (2011)

2010

Marek Cygan, Marcin Pilipczuk: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42): 3701-3713 (2010)

Marek Cygan, Lukasz Kowalik, Borut Luzar: A Planar Linear Arboricity Conjecture. CIAC 2010: 204-216

Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Irredundant Set Faster Than O(2ⁿ). CIAC 2010: 288-298

Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen: Algorithms for Three Versions of the Shortest Common Superstring Problem. CPM 2010: 299-309

Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Fast Approximation in Subspaces by Doubling Metric Decomposition. ESA (1) 2010: 72-83

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion. IPEC 2010: 95-106

Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Capacitated Domination Faster Than O(2ⁿ). SWAT 2010: 74-80

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. WG 2010: 147-158

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset feedback vertex set is fixed parameter tractable. CoRR abs/1004.2972 (2010)

Marek Cygan, Marcin Pilipczuk: Bandwidth and Distortion Revisited. CoRR abs/1004.5012 (2010)

Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Dominating Set is Fixed Parameter Tractable in Claw-free Graphs. CoRR abs/1011.6239 (2010)

2009

Marek Cygan, Lukasz Kowalik, Mateusz Wykurz: Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16): 957-961 (2009)

Marek Cygan, Marcin Pilipczuk: Exact and Approximate Bandwidth. ICALP (1) 2009: 304-315

Marek Cygan, Marcin Pilipczuk: Even Faster Exact Bandwidth. CoRR abs/0902.1661 (2009)

Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk: Beyond O*(2^n) in domination-type problems. CoRR abs/0909.4021 (2009)

Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski: Fast Approximation in Subspaces by Doubling Metric Decomposition. CoRR abs/0911.1626 (2009)

2008

Marek Cygan, Marcin Pilipczuk: Faster Exact Bandwidth. WG 2008: 101-109

Marek Cygan, Lukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz: Exponential-Time Approximation of Hard Problems. CoRR abs/0810.4934 (2008)

1	Daniel Binkele-Raible (Daniel Raible)	[j4]
2	Hans L. Bodlaender	[i20]
3	Ljiljana Brankovic	[j4]
4	Rajesh Hemant Chitnis	[c28] [c26] [i24] [i23]
5	Maxime Crochemore	[c7]
6	Holger Dell	[c32] [i10]
7	Matthias Englert	[c36]
8	Henning Fernau	[j4]
9	Fedor V. Fomin	[c14] [i13]
10	Harold N. Gabow	[c27] [i25]
11	Fabrizio Grandoni	[c35] [c33] [i32] [c31] [c17] [i18]
12	Anupam Gupta	[c36]
13	Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi)	[c29] [c28] [c26] [i24] [i23] [i21]
14	Jian-Feng Hou	[j9]
15	Costas S. Iliopoulos	[c7]
16	Telikepalli Kavitha	[c33] [i32]
17	Samir Khuller	[c29] [i21]
18	Joachim Kneis	[j4]
19	Guy Kortsarz	[c30] [i11]
20	Lukasz Kowalik	[j9] [j6] [i16] [c9] [c6] [j1] [i2] [i1]
21	Dieter Kratsch	[j4]
22	Stefan Kratsch	[c25] [i20] [i19] [i12]
23	Marcin Kubica	[c20] [c7]
24	Alexander Langer	[j4]
25	Erik Jan van Leeuwen	[c14] [i13]
26	Stefano Leonardi	[c31] [c17] [i18]
27	Mathieu Liedloff	[j4]
28	Daniel Lokshtanov	[c32] [c13] [c12] [i10]
29	Borut Luzar	[j9] [c9]
30	Dániel Marx	[i29] [c32] [c26] [i24] [c10] [i10]
31	Monaldo Mastrolilli	[c35]
32	Marcin Mucha	[c36] [c17] [i18] [c6] [i2]
33	Jesper Nederlof	[c32] [i20] [i19] [c18] [i17] [i10]
34	Zeev Nutov	[c30] [i11]
35	Yoshio Okamoto	[c32] [i10]
36	Ramamohan Paturi	[c32] [i10]
37	Geevarghese Philip	[j3] [i5]
38	Marcin Pilipczuk	[j15] [j14] [j13] [c34] [i31] [i29] [j12] [j11] [j10] [j8] [j7] [c31] [c28] [c25] [c24] [c23] [c21] [i28] [i26] [i23] [i22] [j5] [j4] [j3] [c19] [c18] [c17] [c16] [c15] [c13] [c12] [c11] [c10] [i18] [i17] [i15] [i14] [i12] [i9] [j2] [c8] [c6] [c5] [c4] [c3] [i8] [i7] [i6] [i5] [c2] [i4] [i3] [i2] [c1] [i1]
39	Michal Pilipczuk	[j13] [c34] [i29] [j12] [j10] [j8] [c28] [c25] [c24] [c23] [c21] [i28] [i26] [i23] [j3] [c19] [c18] [c16] [c15] [c13] [c12] [c11] [c10] [i17] [i15] [i14] [i12] [i9] [c5] [c3] [i8] [i7] [i5]
40	Jakub Radoszewski	[c20] [c7]
41	Johan M. M. van Rooij	[c18] [i17]
42	Peter Rossmanith	[j4]
43	Wojciech Rytter	[c20] [c7]
44	Piotr Sankowski	[c36] [c31] [c27] [i25] [c17] [i18] [c6] [i2]
45	Saket Saurabh	[c32] [c13] [c12] [i10]
46	Ildikó Schlotter	[c10]
47	Riste Skrekovski	[j15]
48	Magnus Wahlström	[c32] [c25] [i12] [i10]
49	Tomasz Walen	[c20] [c7]
50	Jakub Onufry Wojtaszczyk	[j13] [j12] [j10] [j8] [c24] [c23] [i28] [j5] [j4] [j3] [c19] [c18] [c16] [c15] [c11] [i17] [i15] [i14] [c8] [c5] [c4] [c3] [i8] [i7] [i5] [i3]
51	Jian-Liang Wu	[j9]
52	Mateusz Wykurz	[j1] [i1]

Marek Cygan

Coauthor Index