default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMarcin Pilipczuk
Person information
- affiliation: University of Warsaw, Faculty of Mathematics, Informatics and Mechanics, Poland
SPARQL queries 
🛈 Please note that only 70% of the records listed on this page have a DOI. Therefore, DOI-based queries can only provide partial results.
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j86]Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak:
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path. Comb. 44(2): 417-427 (2024)- [j85]Maria Chudnovsky
, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé:
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs. SIAM J. Comput. 53(1): 47-86 (2024) - [j84]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour:
Induced Subgraphs of Bounded Treewidth and the Container Method. SIAM J. Comput. 53(3): 624-647 (2024) - [j83]Eun Jung Kim, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström:
On Weighted Graph Separation Problems and Flow Augmentation. SIAM J. Discret. Math. 38(1): 170-189 (2024) - [j82]Shaohua Li, Marcin Pilipczuk, Manuel Sorge:
Cluster Editing Parameterized above Modification-disjoint P3-packings. ACM Trans. Algorithms 20(1): 3:1-3:43 (2024) - [j81]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation II: Undirected Graphs. ACM Trans. Algorithms 20(2): 12 (2024) - [j80]Konrad Majewski, Tomás Masarík, Jana Masaríková, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski:
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. ACM Trans. Comput. Theory 16(2): 8:1-8:18 (2024) - [c95]George Osipov, Marcin Pilipczuk, Magnus Wahlström:
Parameterized Complexity of MinCSP over the Point Algebra. ESA 2024: 93:1-93:15 - [c94]Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Sparse induced subgraphs in P6-free graphs. SODA 2024: 5291-5299 - [c93]Antonio Casares, Marcin Pilipczuk, Michal Pilipczuk, Uéverton S. Souza, K. S. Thejaswini:
Simple and tight complexity lower bounds for solving Rabin games. SOSA 2024: 160-167 - [c92]Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza:
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. SOSA 2024: 383-395 - [c91]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski:
Max Weight Independent Set in Sparse Graphs with No Long Claws. STACS 2024: 4:1-4:15 - [c90]Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. STOC 2024: 683-691 - [c89]Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:
Combinatorial Correlation Clustering. STOC 2024: 1617-1628 - [i109]Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:
Combinatorial Correlation Clustering. CoRR abs/2404.05433 (2024) - [i108]Romain Bourneuf, Marcin Pilipczuk:
Bounding ϵ-scatter dimension via metric sparsity. CoRR abs/2410.10191 (2024) - [i107]Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michal Pilipczuk:
Embedding Planar Graphs into Graphs of Treewidth O(log3 n). CoRR abs/2411.00216 (2024) - 2023
- [j79]Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge:
The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. Algorithmica 85(5): 1202-1250 (2023) - [j78]Linda Cook, Tomás Masarík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza:
Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of $P_4$. Electron. J. Comb. 30(3) (2023) - [c88]Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms:
The Influence of Dimensions on the Complexity of Computing Decision Trees. AAAI 2023: 8343-8350 - [c87]Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk:
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS 2023: 2262-2277 - [c86]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma:
Parameterized Complexity Classification for Interval Constraints. IPEC 2023: 11:1-11:19 - [c85]Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza:
A tight quasi-polynomial bound for Global Label Min-Cut. SODA 2023: 290-303 - [c84]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA 2023: 3218-3228 - [c83]Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge:
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. SODA 2023: 3229-3244 - [i106]Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak:
Tight bound on treedepth in terms of pathwidth and longest path. CoRR abs/2302.02995 (2023) - [i105]Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk:
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. CoRR abs/2304.07268 (2023) - [i104]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma:
Parameterized Complexity Classification for Interval Constraints. CoRR abs/2305.13889 (2023) - [i103]Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. CoRR abs/2305.15738 (2023) - [i102]Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Sparse induced subgraphs in P_6-free graphs. CoRR abs/2307.07330 (2023) - [i101]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski:
Max Weight Independent Set in sparse graphs with no long claws. CoRR abs/2309.16995 (2023) - [i100]George Osipov, Marcin Pilipczuk:
Directed Symmetric Multicut is W[1]-hard. CoRR abs/2310.05839 (2023) - [i99]Marcin Pilipczuk, Pawel Rzazewski:
A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number. CoRR abs/2310.11573 (2023) - [i98]Antonio Casares, Marcin Pilipczuk, Michal Pilipczuk, Uéverton S. Souza, K. S. Thejaswini:
Simple and tight complexity lower bounds for solving Rabin games. CoRR abs/2310.20433 (2023) - [i97]Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza:
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR abs/2311.05913 (2023) - 2022
- [j77]Yixin Cao, Marcin Pilipczuk:
Preface to the Special Issue on Parameterized and Exact Computation. Algorithmica 84(8): 2240-2241 (2022) - [j76]Shaohua Li, Marcin Pilipczuk:
Hardness of Metric Dimension in Graphs of Constant Treewidth. Algorithmica 84(11): 3110-3155 (2022) - [j75]Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge:
Packing Directed Cycles Quarter- and Half-Integrally. Comb. 42(Supplement 2): 1409-1438 (2022) - [j74]Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge:
Constant Congestion Brambles. Discret. Math. Theor. Comput. Sci. 24(1) (2022) - [j73]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. SIAM J. Comput. 51(2): 254-289 (2022) - [j72]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput. 51(6): 1866-1930 (2022) - [j71]Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge:
Constant Congestion Brambles in Directed Graphs. SIAM J. Discret. Math. 36(2): 922-938 (2022) - [j70]Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs. ACM Trans. Algorithms 18(1): 4:1-4:57 (2022) - [j69]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) - [c82]Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza:
Taming Graphs with No Large Creatures and Skinny Ladders. ESA 2022: 58:1-58:8 - [c81]Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski:
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. ICALP 2022: 93:1-93:19 - [c80]Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk:
On the Complexity of Problems on Tree-Structured Graphs. IPEC 2022: 6:1-6:17 - [c79]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. STOC 2022: 914-923 - [c78]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Directed flow-augmentation. STOC 2022: 938-947 - [c77]Hugo Jacob, Marcin Pilipczuk:
Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs. WG 2022: 287-299 - [i96]Hugo Jacob, Marcin Pilipczuk:
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. CoRR abs/2201.09749 (2022) - [i95]Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski:
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument. CoRR abs/2203.04836 (2022) - [i94]Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza:
Taming graphs with no large creatures and skinny ladders. CoRR abs/2205.01191 (2022) - [i93]Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms:
The Influence of Dimensions on the Complexity of Computing Decision Trees. CoRR abs/2205.07756 (2022) - [i92]Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk:
On the Complexity of Problems on Tree-structured Graphs. CoRR abs/2206.11828 (2022) - [i91]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. CoRR abs/2207.07422 (2022) - [i90]Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge:
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. CoRR abs/2207.07425 (2022) - [i89]Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza:
A tight quasi-polynomial bound for Global Label Min-Cut. CoRR abs/2207.07426 (2022) - [i88]Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström:
On weighted graph separation problems and flow-augmentation. CoRR abs/2208.14841 (2022) - [i87]Linda Cook, Tomás Masarík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza:
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4. CoRR abs/2209.06171 (2022) - [i86]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Highly unbreakable graph with a fixed excluded minor are almost rigid. CoRR abs/2210.14629 (2022) - [i85]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor. CoRR abs/2210.14638 (2022) - 2021
- [j68]Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk, Blair D. Sullivan:
Polynomial Treedepth Bounds in Linear Colorings. Algorithmica 83(1): 361-386 (2021) - [j67]Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs. Electron. J. Comb. 28(1): 1 (2021) - [j66]Marthe Bonamy, François Dross, Tomás Masarík, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk:
Jones' Conjecture in Subcubic Graphs. Electron. J. Comb. 28(4) (2021) - [j65]Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon:
(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2: Bounds on treewidth. J. Graph Theory 97(4): 624-641 (2021) - [j64]Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk:
Improved Bounds for the Excluded-Minor Approximation of Treedepth. SIAM J. Discret. Math. 35(2): 934-947 (2021) - [j63]Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen:
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. SIAM J. Discret. Math. 35(4): 2387-2429 (2021) - [j62]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) - [c76]Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk:
Close Relatives (Of Feedback Vertex Set), Revisited. IPEC 2021: 21:1-21:15 - [c75]Shaohua Li, Marcin Pilipczuk:
Hardness of Metric Dimension in Graphs of Constant Treewidth. IPEC 2021: 24:1-24:13 - [c74]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Solving hard cut problems via flow-augmentation. SODA 2021: 149-168 - [c73]Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz:
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. SODA 2021: 796-809 - [c72]Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge:
Optimal Discretization is Fixed-parameter Tractable. SODA 2021: 1702-1719 - [c71]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour:
Induced subgraphs of bounded treewidth and the container method. SODA 2021: 1948-1964 - [c70]Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths. SOSA 2021: 204-209 - [c69]Shaohua Li, Marcin Pilipczuk, Manuel Sorge:
Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings. STACS 2021: 49:1-49:16 - [c68]Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time. STOC 2021: 330-341 - [i84]Shaohua Li, Marcin Pilipczuk:
Hardness of Metric Dimension in Graphs of Constant Treewidth. CoRR abs/2102.09791 (2021) - [i83]Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge:
Constant congestion brambles in directed graphs. CoRR abs/2103.08445 (2021) - [i82]Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk:
Close relatives (of Feedback Vertex Set), revisited. CoRR abs/2106.16015 (2021) - [i81]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Directed flow-augmentation. CoRR abs/2111.03450 (2021) - 2020
- [j61]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted Directed Cuts. Algorithmica 82(8): 2135-2155 (2020) - [j60]Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois:
Two lower bounds for $p$-centered colorings. Discret. Math. Theor. Comput. Sci. 22(4) (2020) - [j59]Marcin Pilipczuk, Manuel Sorge:
A Double Exponential Lower Bound for the Distinct Vectors Problem. Discret. Math. Theor. Comput. Sci. 22(4) (2020) - [j58]Shaohua Li, Marcin Pilipczuk:
An Improved FPT Algorithm for Independent Feedback Vertex Set. Theory Comput. Syst. 64(8): 1317-1330 (2020) - [j57]Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé:
On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five. SIAM J. Discret. Math. 34(2): 1472-1483 (2020) - [j56]Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff:
Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms 16(1): 1:1-1:2 (2020) - [c67]Marcin Pilipczuk:
Surprising Applications of Treewidth Bounds for Planar Graphs. Treewidth, Kernels, and Algorithms 2020: 173-188 - [c66]Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge:
The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. ISAAC 2020: 59:1-59:15 - [c65]Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki:
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. IPEC 2020: 37:1-37:18 - [c64]Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé:
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. SODA 2020: 2260-2278 - [e1]Yixin Cao, Marcin Pilipczuk:
15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference). LIPIcs 180, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-172-6 [contents] - [i80]Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon:
(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth. CoRR abs/2001.01607 (2020) - [i79]Marcin Pilipczuk, Manuel Sorge:
A Double Exponential Lower Bound for the Distinct Vectors Problem. CoRR abs/2002.01293 (2020) - [i78]Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge:
Optimal Discretization is Fixed-parameter Tractable. CoRR abs/2003.02475 (2020) - [i77]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour:
Induced subgraphs of bounded treewidth and the container method. CoRR abs/2003.05185 (2020) - [i76]Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Covering minimal separators and potential maximal cliques in Pt-free graphs. CoRR abs/2003.12345 (2020) - [i75]Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michal Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz:
On Dynamic Parameterized k-Path. CoRR abs/2006.00571 (2020) - [i74]Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois:
Two lower bounds for $p$-centered colorings. CoRR abs/2006.04113 (2020) - [i73]Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Solving hard cut problems via flow-augmentation. CoRR abs/2007.09018 (2020) - [i72]Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge:
Constant Congestion Brambles. CoRR abs/2008.02133 (2020) - [i71]Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge:
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. CoRR abs/2009.12892 (2020) - [i70]Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs. CoRR abs/2009.13494 (2020)
2010 – 2019
- 2019
- [j55]Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen:
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs. Algorithmica 81(2): 421-438 (2019) - [j54]Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna:
Edge Bipartization Faster than $$2^k$$ 2 k. Algorithmica 81(3): 917-966 (2019) - [j53]Tomasz Kociumaka, Marcin Pilipczuk:
Deleting Vertices to Graphs of Bounded Genus. Algorithmica 81(9): 3655-3691 (2019) - [j52]Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna:
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. Algorithmica 81(10): 3936-3967 (2019) - [j51]Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz:
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. Algorithmica 81(10): 4029-4042 (2019) - [j50]Anita Liebenau, Marcin Pilipczuk, Paul D. Seymour, Sophie Spirkl:
Caterpillars in Erdős-Hajnal. J. Comb. Theory B 136: 33-43 (2019) - [j49]Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness. ACM J. Exp. Algorithmics 24(1): 2.6:1-2.6:34 (2019) - [j48]Michal Ziobro, Marcin Pilipczuk:
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. ACM J. Exp. Algorithmics 24(1): 2.7:1-2.7:18 (2019) - [j47]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput. 48(2): 417-450 (2019) - [c63]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. ESA 2019: 33:1-33:14 - [c62]Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk:
Improved Bounds for the Excluded-Minor Approximation of Treedepth. ESA 2019: 34:1-34:13 - [c61]Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge:
Packing Directed Circuits Quarter-Integrally. ESA 2019: 72:1-72:13 - [c60]Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk:
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. FOCS 2019: 560-581 - [c59]Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. SODA 2019: 1257-1271 - [c58]Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen:
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. STACS 2019: 39:1-39:18 - [i69]Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé:
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five. CoRR abs/1903.04761 (2019) - [i68]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. CoRR abs/1904.10680 (2019) - [i67]Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk:
Improved bounds for the excluded-minor approximation of treedepth. CoRR abs/1904.13077 (2019) - [i66]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
Efficient approximation schemes for uniform-cost clustering problems in planar graphs. CoRR abs/1905.00656 (2019) - [i65]Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge:
Packing directed circuits quarter-integrally. CoRR abs/1907.02494 (2019) - [i64]Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé:
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. CoRR abs/1907.04585 (2019) - [i63]Shaohua Li, Marcin Pilipczuk, Manuel Sorge:
Cluster Editing parameterized above the size of a modification-disjoint P3 packing is para-NP-hard. CoRR abs/1910.08517 (2019) - [i62]Marthe Bonamy, François Dross, Tomás Masarík, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk:
Jones' Conjecture in subcubic graphs. CoRR abs/1912.01570 (2019) - 2018
- [j46]Krzysztof Choromanski, Dvir Falik, Anita Liebenau, Viresh Patel, Marcin Pilipczuk:
Excluding Hooks and their Complements. Electron. J. Comb. 25(3): 3 (2018) - [j45]Chandra Chekuri, Alina Ene, Marcin Pilipczuk:
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. SIAM J. Discret. Math. 32(3): 2134-2160 (2018) - [j44]Bart M. P. Jansen, Marcin Pilipczuk:
Approximation and Kernelization for Chordal Vertex Deletion. SIAM J. Discret. Math. 32(3): 2258-2301 (2018) - [j43]Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graphs. ACM Trans. Algorithms 14(1): 3:1-3:30 (2018) - [j42]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
Subexponential Parameterized Algorithm for Interval Completion. ACM Trans. Algorithms 14(3): 35:1-35:62 (2018) - [j41]Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen:
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Trans. Algorithms 14(4): 53:1-53:73 (2018) - [j40]Marcin Pilipczuk, Magnus Wahlström:
Directed Multicut is W[1]-hard, Even for Four Terminal Pairs. ACM Trans. Comput. Theory 10(3): 13:1-13:18 (2018) - [c57]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. FOCS 2018: 474-484 - [c56]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-Budgeted Directed Cuts. IPEC 2018: 18:1-18:14 - [c55]Krzysztof Kiljan, Marcin Pilipczuk:
Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. SEA 2018: 12:1-12:12 - [c54]Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. SEA 2018: 14:1-14:16 - [c53]Michal Ziobro, Marcin Pilipczuk:
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. SEA 2018: 29:1-29:14 - [c52]Shaohua Li, Marcin Pilipczuk:
An Improved FPT Algorithm for Independent Feedback Vertex Set. WG 2018: 344-355 - [p1]Marcin Pilipczuk, Michal Pilipczuk:
Planar Digraphs. Classes of Directed Graphs 2018: 207-243 - [i61]Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. CoRR abs/1802.09801 (2018) - [i60]Krzysztof Kiljan, Marcin Pilipczuk:
Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. CoRR abs/1803.00925 (2018) - [i59]Michal Ziobro, Marcin Pilipczuk:
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. CoRR abs/1803.00927 (2018) - [i58]Shaohua Li, Marcin Pilipczuk:
An improved FPT algorithm for Independent Feedback Vertex Set. CoRR abs/1803.00937 (2018) - [i57]Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen:
Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs. CoRR abs/1804.04077 (2018) - [i56]Anita Liebenau, Marcin Pilipczuk, Paul D. Seymour, Sophie Spirkl:
Caterpillars in Erdős-Hajnal. CoRR abs/1810.00811 (2018) - [i55]Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen:
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. CoRR abs/1810.01136 (2018) - [i54]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted directed cuts. CoRR abs/1810.06848 (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]Marcin Pilipczuk, Michal Ziobro:
Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization. CoRR abs/1811.07779 (2018) - 2017
- [j39]Marcin Pilipczuk:
A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discret. Appl. Math. 231: 211-216 (2017) - [j38]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256: 62-82 (2017) - [j37]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) - [j36]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. SIAM J. Comput. 46(1): 161-189 (2017) - [j35]Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk:
Editorial. ACM Trans. Algorithms 13(2): 18:1 (2017) - [j34]Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk:
Hardness of Approximation for Strip Packing. ACM Trans. Comput. Theory 9(3): 14:1-14:7 (2017) - [c51]Dániel Marx, Marcin Pilipczuk:
Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. ESA 2017: 59:1-59:15 - [c50]Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna:
Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. IPEC 2017: 23:1-23:13 - [c49]Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz:
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. IPEC 2017: 24:1-24:11 - [c48]Bart M. P. Jansen, Marcin Pilipczuk:
Approximation and Kernelization for Chordal Vertex Deletion. SODA 2017: 1399-1418 - [i51]Tomasz Kociumaka, Marcin Pilipczuk:
Deleting vertices to graphs of bounded genus. CoRR abs/1706.04065 (2017) - [i50]Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz:
An exponential lower bound for cut sparsifiers in planar graphs. CoRR abs/1706.06086 (2017) - [i49]Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna:
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. CoRR abs/1707.01797 (2017) - [i48]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs. CoRR abs/1707.02190 (2017) - [i47]Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs. CoRR abs/1707.05491 (2017) - [i46]Anita Liebenau, Marcin Pilipczuk:
The Erdős-Hajnal conjecture for caterpillars and their complements. CoRR abs/1710.08701 (2017) - 2016
- [j33]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Algorithmica 74(2): 630-642 (2016) - [j32]Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst. 58(2): 357-376 (2016) - [j31]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known Algorithms for Edge Clique Cover are Probably Optimal. SIAM J. Comput. 45(1): 67-83 (2016) - [j30]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) - [c47]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. FOCS 2016: 515-524 - [c46]Chandra Chekuri, Alina Ene, Marcin Pilipczuk:
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. ICALP 2016: 7:1-7:14 - [c45]Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna:
Edge Bipartization Faster Than 2^k. IPEC 2016: 26:1-26:13 - [c44]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
Subexponential parameterized algorithm for Interval Completion. SODA 2016: 1116-1131 - [c43]Marcin Pilipczuk, Magnus Wahlström:
Directed multicut is W[1]-hard, even for four terminal pairs. SODA 2016: 1167-1178 - [c42]Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graphs. SODA 2016: 1784-1803 - [c41]Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar:
Kernelization and Sparseness: the Case of Dominating Set. STACS 2016: 31:1-31:14 - [c40]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower Bounds for Approximation Schemes for Closest String. SWAT 2016: 12:1-12:10 - [c39]Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski:
On Routing Disjoint Paths in Bounded Treewidth Graphs. SWAT 2016: 15:1-15:15 - [r2]Marcin Pilipczuk:
Exact Algorithms on Graphs of Bounded Average Degree. Encyclopedia of Algorithms 2016: 691-694 - [r1]Marcin Pilipczuk:
Planar Directed k-Vertex-Disjoint Paths Problem. Encyclopedia of Algorithms 2016: 1567-1570 - [i45]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. CoRR abs/1604.05999 (2016) - [i44]Bart M. P. Jansen, Marcin Pilipczuk:
Approximation and Kernelization for Chordal Vertex Deletion. CoRR abs/1605.03001 (2016) - [i43]Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk:
Hardness of approximation for strip packing. CoRR abs/1610.07766 (2016) - [i42]Dániel Marx, Marcin Pilipczuk:
Subexponential parameterized algorithms for graphs of polynomial growth. CoRR abs/1610.07778 (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 - [j29]Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243: 75-85 (2015) - [j28]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting Closer to Friends than Enemies, Revisited. Theory Comput. Syst. 56(2): 394-405 (2015) - [j27]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. SIAM J. Discret. Math. 29(1): 122-144 (2015) - [j26]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
A Subexponential Parameterized Algorithm for Proper Interval Completion. SIAM J. Discret. Math. 29(4): 1961-1987 (2015) - [c38]Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych:
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. STOC 2015: 11-20 - [c37]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna:
Polynomial Kernelization for Removing Induced Claws and Diamonds. WG 2015: 440-455 - [i41]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) - [i40]Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graph. CoRR abs/1507.02163 (2015) - [i39]Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna:
Edge Bipartization faster than 2k. CoRR abs/1507.02168 (2015) - [i38]Marcin Pilipczuk, Magnus Wahlström:
Directed multicut is W[1]-hard, even for four terminal pairs. CoRR abs/1507.02178 (2015) - [i37]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Lower bounds for approximation schemes for Closest String. CoRR abs/1509.05809 (2015) - [i36]Marcin Pilipczuk:
A tight lower bound for Vertex Planarization on graphs of bounded treewidth. CoRR abs/1511.08283 (2015) - [i35]Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski:
On Routing Disjoint Paths in Bounded Treewidth Graphs. CoRR abs/1512.01829 (2015) - 2014
- [j25]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014) - [j24]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling Partially Ordered Jobs Faster than 2 n. Algorithmica 68(3): 692-714 (2014) - [j23]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover. Algorithmica 68(4): 940-953 (2014) - [j22]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) - [j21]Tomasz Kociumaka, Marcin Pilipczuk:
Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10): 556-560 (2014) - [j20]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. J. Comput. Syst. Sci. 80(7): 1430-1447 (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) - [j17]Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman:
Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs. ACM Trans. Comput. Theory 7(1): 4:1-4:18 (2014) - [c36]Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
A Fast Branching Algorithm for Cluster Vertex Deletion. CSR 2014: 111-124 - [c35]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
A Subexponential Parameterized Algorithm for Proper Interval Completion. ESA 2014: 173-184 - [c34]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. FOCS 2014: 186-195 - [c33]Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen:
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. FOCS 2014: 276-285 - [c32]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. MFCS (2) 2014: 189-200 - [c31]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum bisection is fixed parameter tractable. STOC 2014: 323-332 - [i34]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
A subexponential parameterized algorithm for Proper Interval Completion. CoRR abs/1402.3472 (2014) - [i33]Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk:
A subexponential parameterized algorithm for Interval Completion. CoRR abs/1402.3473 (2014) - [i32]Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. CoRR abs/1404.0818 (2014) - [i31]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. CoRR abs/1411.4184 (2014) - [i30]Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Somnath Sikdar:
Kernelization and Sparseness: the case of Dominating Set. CoRR abs/1411.4575 (2014) - 2013
- [j16]Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan:
Towards optimal kernel for connected vertex cover in planar graphs. Discret. Appl. Math. 161(7-8): 1154-1161 (2013) - [j15]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) - [j14]Marek Cygan, Marcin Pilipczuk:
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5-6): 179-182 (2013) - [j13]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. SIAM J. Discret. Math. 27(1): 290-309 (2013) - [j12]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) - [c30]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 - [c29]Marek Cygan, Marcin Pilipczuk:
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. ICALP (1) 2013: 364-375 - [c28]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA 2013: 1044-1053 - [c27]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Tight bounds for Parameterized Complexity of Cluster Editing. STACS 2013: 32-43 - [c26]Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen:
Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. STACS 2013: 353-364 - [i29]Marek Cygan, Marcin Pilipczuk:
Faster exponential-time algorithms in graphs of bounded average degree. CoRR abs/1302.3763 (2013) - [i28]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) - [i27]Tomasz Kociumaka, Marcin Pilipczuk:
Faster deterministic Feedback Vertex Set. CoRR abs/1306.3566 (2013) - [i26]Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk:
Fast branching algorithm for Cluster Vertex Deletion. CoRR abs/1306.3877 (2013) - [i25]Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen:
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. CoRR abs/1306.6593 (2013) - [i24]Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych:
Dynamic Steiner Tree in Planar Graphs. CoRR abs/1308.3336 (2013) - [i23]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection is fixed parameter tractable. CoRR abs/1311.2563 (2013) - 2012
- [j11]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) - [j10]Marek Cygan, Marcin Pilipczuk:
Bandwidth and distortion revisited. Discret. Appl. Math. 160(4-5): 494-504 (2012) - [j9]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) - [j8]Marcin Pilipczuk, Michal Pilipczuk, Riste Skrekovski:
Some results on Vizing's conjecture and related problems. Discret. Appl. Math. 160(16-17): 2484-2490 (2012) - [j7]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) - [j6]Marek Cygan, Marcin Pilipczuk:
Even Faster Exact Bandwidth. ACM Trans. Algorithms 8(1): 8:1-8:14 (2012) - [c25]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 - [c24]Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk:
Designing FPT Algorithms for Cut Problems Using Randomized Contractions. FOCS 2012: 460-469 - [c23]Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique Cover and Graph Separation: New Incompressibility Results. ICALP (1) 2012: 254-265 - [c22]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. ICALP (1) 2012: 581-593 - [c21]Marcin Pilipczuk, Michal Pilipczuk:
Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n. IPEC 2012: 3-12 - [c20]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n. LATIN 2012: 195-206 - [c19]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting Closer to Friends Than Enemies, Revisited. MFCS 2012: 296-307 - [c18]Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman:
Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. SWAT 2012: 364-375 - [c17]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
On Group Feedback Vertex Set Parameterized by the Size of the Cutset. WG 2012: 194-205 - [i22]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Sitting closer to friends than enemies, revisited. CoRR abs/1201.1869 (2012) - [i21]Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Fixed-parameter tractability of multicut in directed acyclic graphs. CoRR abs/1202.5749 (2012) - [i20]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk:
Known algorithms for EDGE CLIQUE COVER are probably optimal. CoRR abs/1203.1754 (2012) - [i19]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) - [i18]Marek Cygan, Marcin Pilipczuk:
On fixed-parameter algorithms for Split Vertex Deletion. CoRR abs/1208.1248 (2012) - [i17]Marcin Pilipczuk, Michal Pilipczuk:
Finding a maximum induced degenerate subgraph faster than 2^n. CoRR abs/1208.4449 (2012) - 2011
- [j5]Vesna Andova, Saso Bogoev, Darko Dimitrov, Marcin Pilipczuk, Riste Skrekovski:
On the Zagreb index inequality of graphs with prescribed vertex degrees. Discret. Appl. Math. 159(8): 852-858 (2011) - [j4]Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Capacitated domination faster than O(n2). Inf. Process. Lett. 111(23-24): 1099-1103 (2011) - [j3]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) - [j2]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) - [c16]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling Partially Ordered Jobs Faster Than 2 n. ESA 2011: 299-310 - [c15]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 - [c14]Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski:
Approximation Algorithms for Union and Intersection Covering Problems. FSTTCS 2011: 28-40 - [c13]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2011: 449-461 - [c12]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
On Multiway Cut Parameterized above Lower Bounds. IPEC 2011: 1-12 - [c11]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On the Hardness of Losing Width. IPEC 2011: 159-168 - [c10]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover. IPEC 2011: 246-258 - [c9]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 - [c8]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142 - [i16]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) - [i15]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) - [i14]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
On Multiway Cut parameterized above lower bounds. CoRR abs/1107.1585 (2011) - [i13]Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Scheduling partially ordered jobs faster than 2^n. CoRR abs/1108.0810 (2011) - [i12]Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan:
Towards optimal kernel for connected vertex cover in planar graphs. CoRR abs/1110.1964 (2011) - [i11]Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström:
Clique cover and graph separation: New incompressibility results. CoRR abs/1111.0570 (2011) - [i10]Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger:
Subexponential fixed-parameter tractability of cluster editing. CoRR abs/1112.4419 (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
- [j1]Marek Cygan, Marcin Pilipczuk:
Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42): 3701-3713 (2010) - [c7]Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk:
Irredundant Set Faster Than O(2n). CIAC 2010: 288-298 - [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
- [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
[j69] [j62] [j47] [i53] [j38] [j37] [j33] [j32] [j31] [j30] [c40] [b1] [j29] [j28] [c37] [i41] [i37] [j25] [j24] [j23] [j22] [j19] [j18] [c36] [c32] [c31] [i31] [j15] [j14] [j13] [j12] [c30] [c29] [c28] [i29] [i28] [i26] [i23] [j11] [j10] [j9] [j7] [j6] [c25] [c24] [c23] [c20] [c19] [c17] [i22] [i20] [i19] [i18] [j4] [j3] [j2] [c16] [c15] [c14] [c13] [c12] [c11] [c10] [c9] [c8] [i16] [i15] [i14] [i13] [i11] [i9] [j1] [c7] [c6] [c5] [c4] [c3] [i8] [i7] [i6] [i5] [c2] [i4] [i3] [i2] [c1] [i1]
[j85] [c94] [c93] [c90] [i107] [c87] [i105] [i103] [i102] [i98] [j73] [j72] [j70] [j69] [c80] [c79] [i92] [i86] [i85] [j67] [j66] [j62] [c73] [c70] [c68] [j57] [c64] [i76] [i75] [i70] [j54] [j47] [c63] [c60] [c59] [i69] [i68] [i66] [i64] [i62] [j42] [j41] [c57] [p1] [i53] [j38] [j37] [j36] [j34] [i48] [i47] [j33] [j31] [j30] [c47] [c45] [c44] [c41] [c40] [i45] [i43] [b1] [j28] [j27] [j26] [c37] [i41] [i39] [i37] [j25] [j24] [j23] [j22] [j20] [j19] [j18] [c35] [c34] [c33] [c32] [c31] [i34] [i33] [i32] [i31] [i30] [j13] [j12] [c30] [c28] [c27] [c26] [i28] [i25] [i23] [j11] [j9] [j8] [j7] [c24] [c23] [c22] [c21] [c20] [c19] [c17] [i22] [i21] [i20] [i19] [i17] [j2] [c16] [c15] [c13] [c12] [c11] [c10] [c9] [c8] [i15] [i14] [i13] [i11] [i10] [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-12-11 20:43 CET 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:
