default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMarek Cygan
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
2020 – today
- 2024
[j55]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)- [c65]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]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 - [i68]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]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]Michal Nauman, Mateusz Ostaszewski, Marek Cygan:
A Case for Validation Buffer in Pessimistic Actor-Critic. CoRR abs/2403.01014 (2024) - [i65]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]Kevin Qiu, Krzysztof Ciebiera, Pawel Fijalkowski, Marek Cygan, Lukasz Kucinski:
RoboMorph: Evolving Robot Morphology using Large Language Models. CoRR abs/2407.08626 (2024) - 2023
- [c63]Michal Nauman, Marek Cygan:
On Many-Actions Policy Gradient. ICML 2023: 25769-25789 - [i63]Piotr Krzywicki, Krzysztof Ciebiera, Rafal Michaluk, Inga Maziarz, Marek Cygan:
Grasping Student: semi-supervised learning for robotic manipulation. CoRR abs/2303.04452 (2023) - [i62]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]Michal Nauman, Marek Cygan:
Decoupled Actor-Critic. CoRR abs/2310.19527 (2023) - 2022
- [j54]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]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) - [i60]Piotr Tempczyk, Ksawery Smoczynski, Philip Smolenski-Jensen, Marek Cygan:
One Simple Trick to Fix Your Bayesian Neural Network. CoRR abs/2207.13167 (2022) - [i59]Michal Nauman, Marek Cygan:
On All-Action Policy Gradients. CoRR abs/2210.13011 (2022) - [i58]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
- [j52]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) - [c62]Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov:
Minimum Common String Partition: Exact Algorithms. ESA 2021: 35:1-35:16 - [i57]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
- [j51]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]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) - [c61]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 - [i56]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)
2010 – 2019
- 2019
- [j49]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]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]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]Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65(3): 12:1-12:46 (2018) - [j45]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]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) - [c60]Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski:
Online Facility Location with Deletions. ESA 2018: 21:1-21:15 - [i55]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]Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski:
Online Facility Location with Deletions. CoRR abs/1807.03839 (2018) - [i53]Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Michal Pilipczuk, Marcin Pilipczuk, Saket Saurabh:
Randomized contractions meet lean decompositions. CoRR abs/1810.06864 (2018) - [i52]Marek Cygan, Guy Kortsarz, Bundit Laekhanukit:
On subexponential running times for approximating directed Steiner tree and related problems. CoRR abs/1811.00710 (2018) - 2017
- [j43]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256: 62-82 (2017) - [j42]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]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]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) - [c59]Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting. AAAI 2017: 459-465 - [c58]Marek Cygan, Lukasz Kowalik, Arkadiusz Socala:
Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ESA 2017: 30:1-30:14 - [c57]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]Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
On Problems Equivalent to (min, +)-Convolution. ICALP 2017: 22:1-22:15 - [i51]Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk:
On problems equivalent to (min, +)-convolution. CoRR abs/1702.07669 (2017) - [i50]Marek Cygan, Lukasz Kowalik, Arkadiusz Socala:
Improving TSP tours using dynamic programming over tree decomposition. CoRR abs/1703.05559 (2017) - [i49]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]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
- [j39]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]Marek Cygan, Pinar Heggernes:
Foreword: Special Issue on IPEC 2014. Algorithmica 75(2): 255-256 (2016) - [j37]Marek Cygan, Pinar Heggernes:
Erratum to: Foreword: Special Issue on IPEC 2014. Algorithmica 75(2): 257 (2016) - [j36]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]Marek Cygan, Lukasz Jez, Jirí Sgall:
Online Knapsack Revisited. Theory Comput. Syst. 58(1): 153-190 (2016) - [j34]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]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known Algorithms for Edge Clique Cover are Probably Optimal. SIAM J. Comput. 45(1): 67-83 (2016) - [j32]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]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) - [c55]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]Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang:
Online Pricing with Impatient Bidders. SODA 2016: 190-201 - [c53]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]Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski:
Algorithmic Complexity of Power Law Networks. SODA 2016: 1306-1325 - [c51]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]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower Bounds for Approximation Schemes for Closest String. SWAT 2016: 12:1-12:10 - [r2]Marek Cygan:
Exact Algorithms for Bandwidth. Encyclopedia of Algorithms 2016: 664-667 - [r1]Marek Cygan:
Randomized Contraction. Encyclopedia of Algorithms 2016: 1738-1741 - [i47]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]Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk:
Hardness of approximation for H-free edge modification problems. CoRR abs/1606.02688 (2016) - [i45]Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting. CoRR abs/1607.07906 (2016) - 2015
- [b1]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 - [j30]Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243: 75-85 (2015) - [j29]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]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]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]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]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) - [c49]Marek Cygan, Tomasz Kociumaka:
Approximating Upper Degree-Constrained Partial Orientations. APPROX-RANDOM 2015: 212-224 - [c48]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna:
Polynomial Kernelization for Removing Induced Claws and Diamonds. WG 2015: 440-455 - [i44]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]Marek Cygan, Jakub Pachocki, Arkadiusz Socala:
The Hardness of Subgraph Isomorphism. CoRR abs/1504.02876 (2015) - [i42]Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski:
Algorithmic Complexity of Power Law Networks. CoRR abs/1507.02426 (2015) - [i41]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]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower bounds for approximation schemes for Closest String. CoRR abs/1509.05809 (2015) - 2014
- [j24]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014) - [j23]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling Partially Ordered Jobs Faster than 2 n. Algorithmica 68(3): 692-714 (2014) - [j22]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover. Algorithmica 68(4): 940-953 (2014) - [j21]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]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]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]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) - [c47]Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
A Fast Branching Algorithm for Cluster Vertex Deletion. CSR 2014: 111-124 - [c46]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. MFCS (2) 2014: 189-200 - [c45]Marek Cygan, Tomasz Kociumaka:
Constant Factor Approximation for Capacitated k-Center with Outliers. STACS 2014: 251-262 - [c44]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum bisection is fixed parameter tractable. STOC 2014: 323-332 - [e1]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] - [i39]Tomasz Kociumaka, Marek Cygan:
Constant Factor Approximation for Capacitated k-Center with Outliers. CoRR abs/1401.2874 (2014) - [i38]Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach:
Kernelization lower bound for Permutation Pattern Matching. CoRR abs/1406.1158 (2014) - [i37]Marek Cygan, Tomasz Kociumaka:
Approximating Upper Degree-Constrained Partial Orientations. CoRR abs/1408.6157 (2014) - [i36]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. CoRR abs/1411.4184 (2014) - 2013
- [j17]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]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]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]Marek Cygan, Guy Kortsarz, Zeev Nutov:
Steiner Forest Orientation Problems. SIAM J. Discret. Math. 27(3): 1503-1513 (2013) - [j13]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) - [c43]Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract). ESA 2013: 361-372 - [c42]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]Marek Cygan:
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. FOCS 2013: 509-518 - [c40]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]Marek Cygan, Marcin Pilipczuk:
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. ICALP (1) 2013: 364-375 - [c38]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]Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli:
How to Sell Hyperedges: The Hypermatching Assignment Problem. SODA 2013: 342-351 - [c36]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA 2013: 1044-1053 - [c35]Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha:
On Pairwise Spanners. STACS 2013: 209-220 - [c34]Marek Cygan, Stefan Kratsch, Jesper Nederlof:
Fast hamiltonicity checking via bases of perfect matchings. STOC 2013: 301-310 - [c33]Marek Cygan, Lukasz Jez:
Online Knapsack Revisited. WAOA 2013: 144-155 - [i35]Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha:
On Pairwise Spanners. CoRR abs/1301.1999 (2013) - [i34]Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. CoRR abs/1302.3763 (2013) - [i33]Marek Cygan:
Improved approximation for 3-dimensional matching via bounded pathwidth local search. CoRR abs/1304.1424 (2013) - [i32]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]Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. CoRR abs/1305.4914 (2013) - [i30]Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
Fast branching algorithm for Cluster Vertex Deletion. CoRR abs/1306.3877 (2013) - [i29]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection is fixed parameter tractable. CoRR abs/1311.2563 (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. Discret. Appl. Math. 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. Discret. Appl. Math. 160(15): 2131-2141 (2012) - [j9]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]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 Trans. Algorithms 8(1): 8:1-8:14 (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. CCC 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(n2). 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 2n-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(2n). 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(2n). 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)
2000 – 2009
- 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)
Coauthor Index
[j53] [j52] [j49] [i53] [j43] [j41] [j39] [j34] [j33] [j32] [c50] [b1] [j30] [j26] [c48] [i44] [i40] [j24] [j23] [j22] [j21] [j19] [j18] [c47] [c46] [c44] [i36] [j17] [j16] [j15] [j13] [c42] [c39] [c36] [i34] [i32] [i30] [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]
[j53] [j52] [j50] [j49] [j44] [i53] [j43] [j41] [j39] [j33] [j32] [c55] [c53] [c50] [i46] [b1] [j26] [c48] [i44] [i41] [i40] [j24] [j23] [j22] [j21] [j19] [j18] [c46] [c44] [i36] [j15] [j13] [c42] [c36] [i32] [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]
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.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-04 00:28 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
