default search action

combined dblp search
author search
venue search
publication search

ask others

Marek Cygan

> Home > Persons

Person information

affiliation: University of Warsaw, Faculty of Mathematics, Informatics, and Mechanics, Poland

Refine list

refinements active!

zoomed in on ?? of ?? records

view refined list in

export refined list as

showing all ?? records

Books and Theses

see FAQ

What is the meaning of the colors in the publication lists?

2015
[b1]
- view
  authority control:
- export record
  dblp key:
  - books/sp/CyganFKLMPPS15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/books/sp/CyganFKLMPPS15
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555

Journal Articles

see FAQ

What is the meaning of the colors in the publication lists?

2024
[j55]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/access/FilipiakZTFC24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/access/FilipiakZTFC24
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan:
Polite Teacher: Semi-Supervised Instance Segmentation With Mutual Learning and Pseudo-Label Thresholding. IEEE Access 12: 37744-37756 (2024)
2022
[j54]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/ChattopadhyayCRW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/ChattopadhyayCRW22
Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen:
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). SIAM J. Comput. 51(3): 20- (2022)
[j53]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganNPPRW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganNPPRW22
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. ACM Trans. Algorithms 18(2): 17:1-17:31 (2022)
2021
[j52]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganKLPPSW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganKLPPSW21
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström:
Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms 17(1): 6:1-6:30 (2021)
2020
[j51]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/ChalermsookCKLM20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/ChalermsookCKLM20
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. 49(4): 772-810 (2020)
[j50]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/BliznetsCKPM20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/BliznetsCKPM20
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk, Lukás Mach:
Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems. ACM Trans. Algorithms 16(2): 25:1-25:31 (2020)
2019
[j49]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/CyganLPPS19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/CyganLPPS19
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput. 48(2): 417-450 (2019)
[j48]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganMWW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganMWW19
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
On Problems Equivalent to (min, +)-Convolution. ACM Trans. Algorithms 15(1): 14:1-14:25 (2019)
[j47]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganKS19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganKS19
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala:
Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ACM Trans. Algorithms 15(4): 54:1-54:19 (2019)
2018
[j46]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/CyganKN18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/CyganKN18
Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65(3): 12:1-12:46 (2018)
[j45]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/jair/CyganKSS18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jair/CyganKSS18
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting. J. Artif. Intell. Res. 63: 495-513 (2018)
[j44]
- view
  authority control:
- export record
  dblp key:
  - journals/toct/BliznetsCKP18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/toct/BliznetsCKP18
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk:
Hardness of Approximation for H-free Edge Modification Problems. ACM Trans. Comput. Theory 10(2): 9:1-9:32 (2018)
2017
[j43]
- view
  authority control:
- export record
  dblp key:
  - journals/iandc/CyganMPP17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iandc/CyganMPP17
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256: 62-82 (2017)
[j42]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/CyganFGKMPS17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/CyganFGKMPS17
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala:
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64(3): 18:1-18:22 (2017)
[j41]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/mst/CyganPPLW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/mst/CyganPPLW17
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna:
Polynomial Kernelization for Removing Induced Claws and Diamonds. Theory Comput. Syst. 60(4): 615-636 (2017)
[j40]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganGH17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganGH17
Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. ACM Trans. Algorithms 13(3): 43:1-43:22 (2017)
2016
[j39]
- view
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganPP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganPP16
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Algorithmica 74(2): 630-642 (2016)
[j38]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganH16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganH16
Marek Cygan, Pinar Heggernes:
Foreword: Special Issue on IPEC 2014. Algorithmica 75(2): 255-256 (2016)
[j37]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganH16a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganH16a
Marek Cygan, Pinar Heggernes:
Erratum to: Foreword: Special Issue on IPEC 2014. Algorithmica 75(2): 257 (2016)
[j36]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/dam/CyganKRRW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dam/CyganKRRW16
Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen:
Polynomial-time approximation algorithms for weighted LCS problem. Discret. Appl. Math. 204: 38-48 (2016)
[j35]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/mst/CyganJS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/mst/CyganJS16
Marek Cygan, Lukasz Jez, Jirí Sgall:
Online Knapsack Revisited. Theory Comput. Syst. 58(1): 153-190 (2016)
[j34]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/mst/BoralCKP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/mst/BoralCKP16
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst. 58(2): 357-376 (2016)
[j33]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/CyganPP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/CyganPP16
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known Algorithms for Edge Clique Cover are Probably Optimal. SIAM J. Comput. 45(1): 67-83 (2016)
[j32]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/ChitnisCHPP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/ChitnisCHPP16
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk:
Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM J. Comput. 45(4): 1171-1229 (2016)
[j31]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganDLMNOPSW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganDLMNOPSW16
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. ACM Trans. Algorithms 12(3): 41:1-41:24 (2016)
2015
[j30]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/iandc/CyganP15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iandc/CyganP15
Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243: 75-85 (2015)
[j29]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/iandc/BodlaenderCKN15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iandc/BodlaenderCKN15
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243: 86-111 (2015)
[j28]
- view
  authority control:
- export record
  dblp key:
  - journals/ipl/BliznetsCKM15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/ipl/BliznetsCKM15
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach:
Kernelization lower bound for Permutation Pattern Matching. Inf. Process. Lett. 115(5): 527-531 (2015)
[j27]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/CyganGS15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/CyganGS15
Marek Cygan, Harold N. Gabow, Piotr Sankowski:
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings. J. ACM 62(4): 28:1-28:30 (2015)
[j26]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/mst/CyganPPW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/mst/CyganPPW15
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting Closer to Friends than Enemies, Revisited. Theory Comput. Syst. 56(2): 394-405 (2015)
[j25]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/ChitnisCHM15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/ChitnisCHM15
Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx:
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ACM Trans. Algorithms 11(4): 28:1-28:28 (2015)
2014
[j24]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganMPPS14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganMPPS14
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014)
[j23]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganPPW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganPPW14
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling Partially Ordered Jobs Faster than 2 n. Algorithmica 68(3): 692-714 (2014)
[j22]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganLPPS14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganLPPS14
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover. Algorithmica 68(4): 940-953 (2014)
[j21]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganPPW14a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganPPW14a
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n. Algorithmica 70(2): 195-207 (2014)
[j20]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/jcss/BazganCCFFL14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jcss/BazganCCFFL14
Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen:
Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80(7): 1285-1297 (2014)
[j19]
- view
  authority control:
- export record
  dblp key:
  - journals/mst/CyganLPPS14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/mst/CyganLPPS14
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On the Hardness of Losing Width. Theory Comput. Syst. 54(1): 73-82 (2014)
[j18]
- view
  authority control:
- export record
  dblp key:
  - journals/toct/CyganKPPW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/toct/CyganKPPW14
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique Cover and Graph Separation: New Incompressibility Results. ACM Trans. Comput. Theory 6(2): 6:1-6:19 (2014)
2013
[j17]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/dmtcs/CyganPS13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dmtcs/CyganPS13
Marek Cygan, Marcin Pilipczuk, Riste Skrekovski:
A bound on the number of perfect matchings in Klee-graphs. Discret. Math. Theor. Comput. Sci. 15(1): 37-54 (2013)
[j16]
- view
  authority control:
- export record
  dblp key:
  - journals/ipl/CyganP13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/ipl/CyganP13
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)
[j15]
- view
  authority control:
- export record
  dblp key:
  - journals/siamdm/CyganPPW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamdm/CyganPPW13
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. SIAM J. Discret. Math. 27(1): 290-309 (2013)
[j14]
- view
  authority control:
- export record
  dblp key:
  - journals/siamdm/CyganKN13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamdm/CyganKN13
Marek Cygan, Guy Kortsarz, Zeev Nutov:
Steiner Forest Orientation Problems. SIAM J. Discret. Math. 27(3): 1503-1513 (2013)
[j13]
- view
  authority control:
- export record
  dblp key:
  - journals/toct/CyganPPW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/toct/CyganPPW13
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1): 3:1-3:11 (2013)
2012
[j12]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/CyganPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/CyganPPW12
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]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/dam/CyganP12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dam/CyganP12
Marek Cygan, Marcin Pilipczuk:
Bandwidth and distortion revisited. Discret. Appl. Math. 160(4-5): 494-504 (2012)
[j10]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/dam/CyganPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dam/CyganPPW12
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Kernelization hardness of connectivity problems in d-degenerate graphs. Discret. Appl. Math. 160(15): 2131-2141 (2012)
[j9]
- view
  authority control:
- export record
  dblp key:
  - journals/jgt/CyganHKLW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jgt/CyganHKLW12
Marek Cygan, Jianfeng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang Wu:
A Planar linear arboricity conjecture. J. Graph Theory 69(4): 403-425 (2012)
[j8]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/CyganPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/CyganPPW12
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]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/CyganP12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/CyganP12
Marek Cygan, Marcin Pilipczuk:
Even Faster Exact Bandwidth. ACM Trans. Algorithms 8(1): 8:1-8:14 (2012)
2011
[j6]
- view
  authority control:
- export record
  dblp key:
  - journals/ipl/CyganK11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/ipl/CyganK11
Marek Cygan, Lukasz Kowalik:
Channel assignment via fast zeta transform. Inf. Process. Lett. 111(15): 727-730 (2011)
[j5]
- view
  authority control:
- export record
  dblp key:
  - journals/ipl/CyganPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/ipl/CyganPW11
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Capacitated domination faster than O(n²). Inf. Process. Lett. 111(23-24): 1099-1103 (2011)
[j4]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/jda/Binkele-RaibleBCFKKLLPRW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jda/Binkele-RaibleBCFKKLLPRW11
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]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/tcs/CyganPPPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/tcs/CyganPPPW11
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)
2010
[j2]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/tcs/CyganP10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/tcs/CyganP10
Marek Cygan, Marcin Pilipczuk:
Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42): 3701-3713 (2010)
2009
[j1]
- view
  authority control:
- export record
  dblp key:
  - journals/ipl/CyganKW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/ipl/CyganKW09
Marek Cygan, Lukasz Kowalik, Mateusz Wykurz:
Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16): 957-961 (2009)

Conference and Workshop Papers

see FAQ

What is the meaning of the colors in the publication lists?

2024
[c65]
- view
  - electronic edition @ openreview.net (open access)
  - no references & citations available
- export record
  dblp key:
  - conf/icml/LudziejewskiKAP24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/LudziejewskiKAP24
Jan Ludziejewski, Jakub Krajewski, Kamil Adamczewski, Maciej Pióro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur:
Scaling Laws for Fine-Grained Mixture of Experts. ICML 2024
[c64]
- view
  - electronic edition @ openreview.net (open access)
  - no references & citations available
- export record
  dblp key:
  - conf/icml/NaumanBMTOC24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/NaumanBMTOC24
Michal Nauman, Michal Bortkiewicz, Piotr Milos, Tomasz Trzcinski, Mateusz Ostaszewski, Marek Cygan:
Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning. ICML 2024
2023
[c63]
- view
  - electronic edition @ mlr.press (open access)
  - no references & citations available
- export record
  dblp key:
  - conf/icml/NaumanC23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/NaumanC23
Michal Nauman, Marek Cygan:
On Many-Actions Policy Gradient. ICML 2023: 25769-25789
2021
[c62]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/esa/CyganKMNR21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganKMNR21
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov:
Minimum Common String Partition: Exact Algorithms. ESA 2021: 35:1-35:16
2020
[c61]
- view
  authority control:
- export record
  dblp key:
  - conf/waoa/HalldorssonKC20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/waoa/HalldorssonKC20
Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan:
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. WAOA 2020: 159-173
2018
[c60]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/esa/CyganCMS18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganCMS18
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski:
Online Facility Location with Deletions. ESA 2018: 21:1-21:15
2017
[c59]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/aaai/CyganKSS17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aaai/CyganKSS17
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting. AAAI 2017: 459-465
[c58]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/esa/CyganKS17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganKS17
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala:
Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ESA 2017: 30:1-30:14
[c57]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/ChalermsookCKLM17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/ChalermsookCKLM17
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS 2017: 743-754
[c56]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/CyganMWW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CyganMWW17
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
On Problems Equivalent to (min, +)-Convolution. ICALP 2017: 22:1-22:15
2016
[c55]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/approx/BliznetsCKP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BliznetsCKP16
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk:
Hardness of Approximation for H-Free Edge Modification Problems. APPROX-RANDOM 2016: 3:1-3:17
[c54]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/CyganMSZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CyganMSZ16
Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang:
Online Pricing with Impatient Bidders. SODA 2016: 190-201
[c53]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BliznetsCKMP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BliznetsCKMP16
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk:
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. SODA 2016: 1132-1151
[c52]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BrachCLS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BrachCLS16
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski:
Algorithmic Complexity of Power Law Networks. SODA 2016: 1306-1325
[c51]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/CyganFGKMPS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CyganFGKMPS16
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala:
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA 2016: 1643-1649
[c50]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/swat/CyganLPPS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/swat/CyganLPPS16
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower Bounds for Approximation Schemes for Closest String. SWAT 2016: 12:1-12:10
2015
[c49]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/approx/CyganK15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/CyganK15
Marek Cygan, Tomasz Kociumaka:
Approximating Upper Degree-Constrained Partial Orientations. APPROX-RANDOM 2015: 212-224
[c48]
- view
  authority control:
- export record
  dblp key:
  - conf/wg/CyganPPLW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wg/CyganPPLW15
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna:
Polynomial Kernelization for Removing Induced Claws and Diamonds. WG 2015: 440-455
2014
[c47]
- view
  authority control:
- export record
  dblp key:
  - conf/csr/BoralCKP14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/csr/BoralCKP14
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
A Fast Branching Algorithm for Cluster Vertex Deletion. CSR 2014: 111-124
[c46]
- view
  authority control:
- export record
  dblp key:
  - conf/mfcs/CyganMPP14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/mfcs/CyganMPP14
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. MFCS (2) 2014: 189-200
[c45]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/stacs/CyganK14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stacs/CyganK14
Marek Cygan, Tomasz Kociumaka:
Constant Factor Approximation for Capacitated k-Center with Outliers. STACS 2014: 251-262
[c44]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/CyganLPPS14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/CyganLPPS14
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum bisection is fixed parameter tractable. STOC 2014: 323-332
2013
[c43]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/CyganGH13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganGH13
Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract). ESA 2013: 361-372
[c42]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/CyganMPP13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/CyganMPP13
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. FOCS 2013: 197-206
[c41]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/Cygan13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/Cygan13
Marek Cygan:
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. FOCS 2013: 509-518
[c40]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/BodlaenderCKN13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/BodlaenderCKN13
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. ICALP (1) 2013: 196-207
[c39]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/CyganP13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CyganP13
Marek Cygan, Marcin Pilipczuk:
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. ICALP (1) 2013: 364-375
[c38]
- view
  authority control:
- export record
  dblp key:
  - conf/innovations/CyganEGMS13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/CyganEGMS13
Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski:
Catch them if you can: how to serve impatient users. ITCS 2013: 485-494
[c37]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/soda/CyganGM13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CyganGM13
Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli:
How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013: 342-351
[c36]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/soda/CyganPP13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CyganPP13
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA 2013: 1044-1053
[c35]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/stacs/CyganGK13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stacs/CyganGK13
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha:
On Pairwise Spanners. STACS 2013: 209-220
[c34]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/CyganKN13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/CyganKN13
Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast hamiltonicity checking via bases of perfect matchings. STOC 2013: 301-310
[c33]
- view
  authority control:
- export record
  dblp key:
  - conf/waoa/CyganJ13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/waoa/CyganJ13
Marek Cygan, Lukasz Jez:
Online Knapsack Revisited. WAOA 2013: 144-155
2012
[c32]
- view
  authority control:
- export record
  dblp key:
  - conf/coco/CyganDLMNOPSW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/coco/CyganDLMNOPSW12
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. CCC 2012: 74-84
[c31]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/CyganGLPS12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganGLPS12
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]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/CyganKN12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganKN12
Marek Cygan, Guy Kortsarz, Zeev Nutov:
Steiner Forest Orientation Problems. ESA 2012: 361-372
[c29]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/CyganHK12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/CyganHK12
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller:
LP Rounding for k-Centers with Non-uniform Hard Capacities. FOCS 2012: 273-282
[c28]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/ChitnisCHPP12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/ChitnisCHPP12
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]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/CyganGS12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/CyganGS12
Marek Cygan, Harold N. Gabow, Piotr Sankowski:
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. FOCS 2012: 531-540
[c26]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/ChitnisCHM12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/ChitnisCHM12
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]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/CyganKPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CyganKPPW12
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]
- view
  authority control:
- export record
  dblp key:
  - conf/latin/CyganPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/latin/CyganPPW12
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]
- view
  authority control:
- export record
  dblp key:
  - conf/mfcs/CyganPPW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/mfcs/CyganPPW12
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting Closer to Friends Than Enemies, Revisited. MFCS 2012: 296-307
[c22]
- view
  authority control:
- export record
  dblp key:
  - conf/swat/Cygan12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/swat/Cygan12
Marek Cygan:
Deterministic Parameterized Connected Vertex Cover. SWAT 2012: 95-106
[c21]
- view
  authority control:
- export record
  dblp key:
  - conf/wg/CyganPP12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wg/CyganPP12
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
On Group Feedback Vertex Set Parameterized by the Size of the Cutset. WG 2012: 194-205
2011
[c20]
- view
  authority control:
- export record
  dblp key:
  - conf/cpm/CyganKRRW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/cpm/CyganKRRW11
Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen:
Polynomial-Time Approximation Algorithms for Weighted LCS Problem. CPM 2011: 455-466
[c19]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/CyganPPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganPPW11
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling Partially Ordered Jobs Faster Than 2 n. ESA 2011: 299-310
[c18]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/CyganNPPRW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/CyganNPPRW11
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]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - conf/fsttcs/CyganGLMPS11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/fsttcs/CyganGLMPS11
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]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/CyganPPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CyganPPW11
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2011: 449-461
[c15]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/CyganPPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/CyganPPW11
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
On Multiway Cut Parameterized above Lower Bounds. IPEC 2011: 1-12
[c14]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/CyganFL11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/CyganFL11
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen:
Parameterized Complexity of Firefighting Revisited. IPEC 2011: 13-26
[c13]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/CyganLPPS11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/CyganLPPS11
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On the Hardness of Losing Width. IPEC 2011: 159-168
[c12]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/CyganLPPS11a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/CyganLPPS11a
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover. IPEC 2011: 246-258
[c11]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/CyganPPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CyganPPW11
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]
- view
  authority control:
- export record
  dblp key:
  - conf/wg/CyganMPPS11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wg/CyganMPPS11
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142
2010
[c9]
- view
  authority control:
- export record
  dblp key:
  - conf/ciac/CyganKL10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/ciac/CyganKL10
Marek Cygan, Lukasz Kowalik, Borut Luzar:
A Planar Linear Arboricity Conjecture. CIAC 2010: 204-216
[c8]
- view
  authority control:
- export record
  dblp key:
  - conf/ciac/CyganPW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/ciac/CyganPW10
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Irredundant Set Faster Than O(2ⁿ). CIAC 2010: 288-298
[c7]
- view
  authority control:
- export record
  dblp key:
  - conf/cpm/CrochemoreCIKRRW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/cpm/CrochemoreCIKRRW10
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]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/CyganKMPS10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CyganKMPS10
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski:
Fast Approximation in Subspaces by Doubling Metric Decomposition. ESA (1) 2010: 72-83
[c5]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/CyganPPW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/CyganPPW10
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]
- view
  authority control:
- export record
  dblp key:
  - conf/swat/CyganPW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/swat/CyganPW10
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Capacitated Domination Faster Than O(2ⁿ). SWAT 2010: 74-80
[c3]
- view
  authority control:
- export record
  dblp key:
  - conf/wg/CyganPPW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wg/CyganPPW10
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. WG 2010: 147-158
2009
[c2]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/CyganP09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CyganP09
Marek Cygan, Marcin Pilipczuk:
Exact and Approximate Bandwidth. ICALP (1) 2009: 304-315
2008
[c1]
- view
  authority control:
- export record
  dblp key:
  - conf/wg/CyganP08
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wg/CyganP08
Marek Cygan, Marcin Pilipczuk:
Faster Exact Bandwidth. WG 2008: 101-109

Editorship

see FAQ

What is the meaning of the colors in the publication lists?

2014
[e1]
- view
  authority control:
- export record
  dblp key:
  - conf/iwpec/2014
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iwpec/2014
Marek Cygan, Pinar Heggernes:
Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers. Lecture Notes in Computer Science 8894, Springer 2014, ISBN 978-3-319-13523-6 [contents]

Reference Works

see FAQ

What is the meaning of the colors in the publication lists?

2016
[r2]
- view
  authority control:
- export record
  dblp key:
  - reference/algo/Cygan16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/reference/algo/Cygan16
Marek Cygan:
Exact Algorithms for Bandwidth. Encyclopedia of Algorithms 2016: 664-667
[r1]
- view
  authority control:
- export record
  dblp key:
  - reference/algo/Cygan16a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/reference/algo/Cygan16a
Marek Cygan:
Randomized Contraction. Encyclopedia of Algorithms 2016: 1738-1741

Informal and Other Publications

see FAQ

What is the meaning of the colors in the publication lists?

2024
[i68]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2402-07871
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2402-07871
Jakub Krajewski, Jan Ludziejewski, Kamil Adamczewski, Maciej Pióro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur:
Scaling Laws for Fine-Grained Mixture of Experts. CoRR abs/2402.07871 (2024)
[i67]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2403-00514
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2403-00514
Michal Nauman, Michal Bortkiewicz, Mateusz Ostaszewski, Piotr Milos, Tomasz Trzcinski, Marek Cygan:
Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning. CoRR abs/2403.00514 (2024)
[i66]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2403-01014
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2403-01014
Michal Nauman, Mateusz Ostaszewski, Marek Cygan:
A Case for Validation Buffer in Pessimistic Actor-Critic. CoRR abs/2403.01014 (2024)
[i65]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2405-16158
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2405-16158
Michal Nauman, Mateusz Ostaszewski, Krzysztof Jankowski, Piotr Milos, Marek Cygan:
Bigger, Regularized, Optimistic: scaling for compute and sample-efficient continuous control. CoRR abs/2405.16158 (2024)
[i64]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2407-08626
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2407-08626
Kevin Qiu, Krzysztof Ciebiera, Pawel Fijalkowski, Marek Cygan, Lukasz Kucinski:
RoboMorph: Evolving Robot Morphology using Large Language Models. CoRR abs/2407.08626 (2024)
2023
[i63]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2303-04452
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2303-04452
Piotr Krzywicki, Krzysztof Ciebiera, Rafal Michaluk, Inga Maziarz, Marek Cygan:
Grasping Student: semi-supervised learning for robotic manipulation. CoRR abs/2303.04452 (2023)
[i62]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2310-15961
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2310-15961
Szymon Antoniak, Sebastian Jaszczur, Michal Krutul, Maciej Pióro, Jakub Krajewski, Jan Ludziejewski, Tomasz Odrzygózdz, Marek Cygan:
Mixture of Tokens: Efficient LLMs through Cross-Example Aggregation. CoRR abs/2310.15961 (2023)
[i61]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2310-19527
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2310-19527
Michal Nauman, Marek Cygan:
Decoupled Actor-Critic. CoRR abs/2310.19527 (2023)
2022
[i60]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2207-13167
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2207-13167
Piotr Tempczyk, Ksawery Smoczynski, Philip Smolenski-Jensen, Marek Cygan:
One Simple Trick to Fix Your Bayesian Neural Network. CoRR abs/2207.13167 (2022)
[i59]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2210-13011
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2210-13011
Michal Nauman, Marek Cygan:
On All-Action Policy Gradients. CoRR abs/2210.13011 (2022)
[i58]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2211-03850
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2211-03850
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan:
Polite Teacher: Semi-Supervised Instance Segmentation with Mutual Learning and Pseudo-Label Thresholding. CoRR abs/2211.03850 (2022)
2021
[i57]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-2112-07528
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2112-07528
Dominik Filipiak, Piotr Tempczyk, Marek Cygan:
n-CPS: Generalising Cross Pseudo Supervision to n networks for Semi-Supervised Semantic Segmentation. CoRR abs/2112.07528 (2021)
2020
[i56]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-2008-05374
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2008-05374
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz:
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. CoRR abs/2008.05374 (2020)
2018
[i55]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1802-05992
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1802-05992
Maciej Jaskowski, Jakub Swiatkowski, Michal Zajac, Maciej Klimek, Jarek Potiuk, Piotr Rybicki, Piotr Polatowski, Przemyslaw Walczyk, Kacper Nowicki, Marek Cygan:
Improved GQ-CNN: Deep Learning Model for Planning Robust Grasps. CoRR abs/1802.05992 (2018)
[i54]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1807-03839
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1807-03839
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski:
Online Facility Location with Deletions. CoRR abs/1807.03839 (2018)
[i53]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1810-06864
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1810-06864
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Michal Pilipczuk, Marcin Pilipczuk, Saket Saurabh:
Randomized contractions meet lean decompositions. CoRR abs/1810.06864 (2018)
[i52]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1811-00710
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1811-00710
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit:
On subexponential running times for approximating directed Steiner tree and related problems. CoRR abs/1811.00710 (2018)
2017
[i51]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganMWW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganMWW17
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
On problems equivalent to (min, +)-convolution. CoRR abs/1702.07669 (2017)
[i50]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganKS17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganKS17
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala:
Improving TSP tours using dynamic programming over tree decomposition. CoRR abs/1703.05559 (2017)
[i49]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1708-04218
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1708-04218
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR abs/1708.04218 (2017)
[i48]
- view
  - electronic edition via DOI (open access)
  - references & citations
  authority control:
- export record
  dblp key:
  - journals/dagstuhl-reports/CyganFHW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dagstuhl-reports/CyganFHW17
Marek Cygan, Fedor V. Fomin, Danny Hermelin, Magnus Wahlström:
Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). Dagstuhl Reports 7(1): 103-128 (2017)
2016
[i47]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganFGKMPS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganFGKMPS16
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala:
Tight Lower Bounds on Graph Embedding Problems. CoRR abs/1602.05016 (2016)
[i46]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/BliznetsCKP16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BliznetsCKP16
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk:
Hardness of approximation for H-free edge modification problems. CoRR abs/1606.02688 (2016)
[i45]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganKSS16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganKSS16
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting. CoRR abs/1607.07906 (2016)
2015
[i44]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganPPLW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganPPLW15
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna:
Polynomial kernelization for removing induced claws and diamonds. CoRR abs/1503.00704 (2015)
[i43]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganPS15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganPS15
Marek Cygan, Jakub Pachocki, Arkadiusz Socala:
The Hardness of Subgraph Isomorphism. CoRR abs/1504.02876 (2015)
[i42]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/BrachCLS15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BrachCLS15
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski:
Algorithmic Complexity of Power Law Networks. CoRR abs/1507.02426 (2015)
[i41]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/BliznetsCKMP15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BliznetsCKMP15
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk:
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems. CoRR abs/1508.05282 (2015)
[i40]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganLPPS15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganLPPS15
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower bounds for approximation schemes for Closest String. CoRR abs/1509.05809 (2015)
2014
[i39]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/KociumakaC14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/KociumakaC14
Tomasz Kociumaka, Marek Cygan:
Constant Factor Approximation for Capacitated k-Center with Outliers. CoRR abs/1401.2874 (2014)
[i38]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/BliznetsCKM14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BliznetsCKM14
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach:
Kernelization lower bound for Permutation Pattern Matching. CoRR abs/1406.1158 (2014)
[i37]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganK14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganK14
Marek Cygan, Tomasz Kociumaka:
Approximating Upper Degree-Constrained Partial Orientations. CoRR abs/1408.6157 (2014)
[i36]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganMPP14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganMPP14
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. CoRR abs/1411.4184 (2014)
2013
[i35]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1301-1999
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1301-1999
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha:
On Pairwise Spanners. CoRR abs/1301.1999 (2013)
[i34]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1302-3763
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1302-3763
Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. CoRR abs/1302.3763 (2013)
[i33]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1304-1424
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1304-1424
Marek Cygan:
Improved approximation for 3-dimensional matching via bounded pathwidth local search. CoRR abs/1304.1424 (2013)
[i32]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1304-4207
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1304-4207
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)
[i31]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1305-4914
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1305-4914
Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. CoRR abs/1305.4914 (2013)
[i30]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/BoralCKP13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BoralCKP13
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
Fast branching algorithm for Cluster Vertex Deletion. CoRR abs/1306.3877 (2013)
[i29]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/CyganLPPS13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CyganLPPS13
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection is fixed parameter tractable. CoRR abs/1311.2563 (2013)
2012
[i28]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1201-1869
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1201-1869
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting closer to friends than enemies, revisited. CoRR abs/1201.1869 (2012)
[i27]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1202-6642
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1202-6642
Marek Cygan:
Deterministic parameterized connected vertex cover. CoRR abs/1202.6642 (2012)
[i26]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1203-1754
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1203-1754
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known algorithms for EDGE CLIQUE COVER are probably optimal. CoRR abs/1203.1754 (2012)
[i25]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1204-1616
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1204-1616
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1205-1271
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1205-1271
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1207-4079
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1207-4079
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1208-1248
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1208-1248
Marek Cygan, Marcin Pilipczuk:
On fixed-parameter algorithms for Split Vertex Deletion. CoRR abs/1208.1248 (2012)
[i21]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1208-3054
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1208-3054
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller:
LP Rounding for k-Centers with Non-uniform Hard Capacities. CoRR abs/1208.3054 (2012)
[i20]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1211-1505
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1211-1505
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1211-1506
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1211-1506
Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast Hamiltonicity checking via bases of perfect matchings. CoRR abs/1211.1506 (2012)
2011
[i18]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1102-5105
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1102-5105
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1103-0534
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1103-0534
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1103-2275
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1103-2275
Marek Cygan, Lukasz Kowalik:
Channel Assignment via Fast Zeta Transform. CoRR abs/1103.2275 (2011)
[i15]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1107-1585
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1107-1585
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
On Multiway Cut parameterized above lower bounds. CoRR abs/1107.1585 (2011)
[i14]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1108-0810
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1108-0810
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling partially ordered jobs faster than 2^n. CoRR abs/1108.0810 (2011)
[i13]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1109-4729
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1109-4729
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen:
Parameterized Complexity of Firefighting Revisited. CoRR abs/1109.4729 (2011)
[i12]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1111-0570
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1111-0570
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1112-2273
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1112-2273
Marek Cygan, Guy Kortsarz, Zeev Nutov:
Steiner Forest Orientation Problems. CoRR abs/1112.2273 (2011)
[i10]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1112-2275
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1112-2275
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1112-6255
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1112-6255
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
On group feedback vertex set parameterized by the size of the cutset. CoRR abs/1112.6255 (2011)
2010
[i8]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1004-2972
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1004-2972
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset feedback vertex set is fixed parameter tractable. CoRR abs/1004.2972 (2010)
[i7]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1004-5010
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1004-5010
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]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1004-5012
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1004-5012
Marek Cygan, Marcin Pilipczuk:
Bandwidth and Distortion Revisited. CoRR abs/1004.5012 (2010)
[i5]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-1011-6239
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1011-6239
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
[i4]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-0902-1661
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0902-1661
Marek Cygan, Marcin Pilipczuk:
Even Faster Exact Bandwidth. CoRR abs/0902.1661 (2009)
[i3]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-0909-4021
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0909-4021
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Beyond O*(2^n) in domination-type problems. CoRR abs/0909.4021 (2009)
[i2]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-0911-1626
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0911-1626
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski:
Fast Approximation in Subspaces by Doubling Metric Decomposition. CoRR abs/0911.1626 (2009)
2008
[i1]
- view
  - electronic edition @ arxiv.org (open access)
  - references & citations
- export record
  dblp key:
  - journals/corr/abs-0810-4934
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0810-4934
Marek Cygan, Lukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz:
Exponential-Time Approximation of Hard Problems. CoRR abs/0810.4934 (2008)

Coauthor Index

see FAQ

manage site settings

To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.