vix.ing · top · new · best · stats · spec

Michał Pilipczuk

  1. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter\n tractable
    2013/04/15 by Marek Cygan, Cygan, Marek, Dániel Marx +5 · 4 citations
    Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
  2. Designing FPT algorithms for cut problems using randomized contractions
    2012/07/17 by Rajesh Chitnis, Marek Cygan, Chitnis, Rajesh +7 · 5 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
  3. On Multiway Cut parameterized above lower bounds
    2011/07/08 by Marek Cygan, Cygan, Marek, Marcin Pilipczuk +5 · 3 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
  4. Problems parameterized by treewidth tractable in single exponential\n time: a logical approach
    2011/04/15 by Michał Pilipczuk, Pilipczuk, Michał · 3 citations
    Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Model-Driven Software Engineering Techniques
  5. On space efficiency of algorithms working on structural decompositions\n of graphs
    2015/09/19 by Michał Pilipczuk, Pilipczuk, Michał, Marcin Wrochna +1 · 3 citations
    Computer Science · #Algorithms and Data Compression #Advanced Graph Theory Research #semigroups and automata theory
  6. Minor Containment and Disjoint Paths in almost-linear time
    2024/04/05 by Tuukka Korhonen, Michał Pilipczuk, Korhonen, Tuukka +3 · 8 citations
    Business, Management and Accounting · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #Advanced Queuing Theory Analysis #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Simulation Techniques and Applications
  7. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
    2019/07/10 by Maria Chudnovsky, Chudnovsky, Maria, Marcin Pilipczuk +5 · 4 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
  8. Minimum Bisection is fixed parameter tractable
    2013/11/11 by Marek Cygan, Daniel Lokshtanov, Cygan, Marek +7 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  9. Stable graphs of bounded twin-width
    2021/07/08 by Jakub Gajarský, Gajarský, Jakub, Michał Pilipczuk +3 · 3 citations
    Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Logic in Computer Science (cs.LO) #Nuclear Receptors and Signaling
  10. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
    2015/04/21 by Marx, Dániel, Pilipczuk, Michał, Dániel Marx +1 · 2 citations
    Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced Graph Theory Research #Algorithms and Data Compression #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Optimization and Search Problems #Vehicle Routing Optimization Methods #semigroups and automata theory
  11. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
    2020/02/11 by Jesper Nederlof, Michał Pilipczuk, Nederlof, Jesper +5 · 2 citations
    Computer Science · #68Q25 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Graph Theory and Algorithms
  12. Dominating Set is Fixed Parameter Tractable in Claw-free Graphs
    2010/11/29 by Marek Cygan, Geevarghese Philip, Cygan, Marek +7 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems
  13. Clique cover and graph separation: New incompressibility results
    2011/11/02 by Marek Cygan, Cygan, Marek, Stefan Kratsch +7 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
  14. Fixed-parameter tractability of multicut in directed acyclic graphs
    2012/02/26 by Stefan Kratsch, Marcin Pilipczuk, Kratsch, Stefan +5 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Protein Degradation and Inhibitors
  15. Finding a maximum induced degenerate subgraph faster than 2n
    2012/08/22 by Marcin Pilipczuk, Michał Pilipczuk, Pilipczuk, Marcin +1 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
  16. Simpler and faster algorithms for detours in planar digraphs
    2023/01/06 by Meike Hatzel, Konrad Majewski, Hatzel, Meike +5 · 2 citations
    Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
  17. A subexponential parameterized algorithm for Proper Interval Completion
    2014/02/13 by Ivan Bliznets, Fedor V. Fomin, Bliznets, Ivan +5 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #semigroups and automata theory
  18. A Polynomial Kernel for Trivially Perfect Editing
    2014/12/23 by Pål Grønås Drange, Michał Pilipczuk, Drange, Pål Grønås +1 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
  19. Edge Bipartization faster than 2k
    2015/07/08 by Marcin Pilipczuk, Michał Pilipczuk, Pilipczuk, Marcin +3 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
  20. Lower bounds for approximation schemes for Closest String
    2015/09/18 by Marek Cygan, Cygan, Marek, Daniel Lokshtanov +7 · 1 citation
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  21. Linear kernels for edge deletion problems to immersion-closed graph\n classes
    2016/09/25 by Archontia C. Giannopoulou, Michał Pilipczuk, Giannopoulou, Archontia C. +7 · 1 citation
    Computer Science · #05C85 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Machine Learning and Algorithms
  22. Parameterized circuit complexity of model checking first-order logic on\n sparse structures
    2018/05/09 by Michał Pilipczuk, Sebastian Siebertz, Pilipczuk, Michał +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #semigroups and automata theory
  23. Subexponential-time algorithms for finding large induced sparse\n subgraphs
    2019/10/02 by Jana Novotná, Karolina Okrasa, Novotná, Jana +9 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems
  24. Parameterized algorithms for block-structured integer programs with large entries
    2023/11/03 by Jana Cslovjecsek, Martin Koutecký, Cslovjecsek, Jana +7 · 2 citations
    Business, Management and Accounting · Economics, Econometrics and Finance · Engineering · #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms #Supply Chain and Inventory Management
  25. On objects dual to tree-cut decompositions
    2021/03/26 by Łukasz Bożyk, Bożyk, Łukasz, Oscar Defrain +5 · 1 citation
    Economics, Econometrics and Finance · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Sports Analytics and Performance
  26. An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
    2021/03/31 by Daniel Lokshtanov, Pranabendu Misra, Lokshtanov, Daniel +7 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  27. Prime and polynomial distances in colourings of the plane
    2023/08/04 by James C. Davies, Davies, James, Rose McCarty +3 · 1 citation
    Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematics and Applications #Metric Geometry (math.MG) #Number Theory (math.NT)
  28. A polynomial-time OPTε-approximation algorithm for maximum independent set of connected subgraphs in a planar graph
    2023/10/31 by Jana Cslovjecsek, Michał Pilipczuk, Cslovjecsek, Jana +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  29. On coarse tree decompositions and coarse balanced separators
    2025/02/27 by Tara Abrishami, Abrishami, Tara, Jadwiga Czyżewska +9 · 2 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
  30. Fully dynamic approximation schemes on planar and apex-minor-free graphs
    2023/10/31 by Tuukka Korhonen, Wojciech Nadara, Korhonen, Tuukka +5 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  31. Strong odd colorings in graph classes of bounded expansion
    2025/05/21 by Michał Pilipczuk, Pilipczuk, Michał · 2 citations
    Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
  32. Embedding Planar Graphs into Graphs of Treewidth O(log3 n)
    2024/10/31 by Hsien-Chih Chang, Vincent Cohen-Addad, Chang, Hsien-Chih +9 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
  33. Dynamic domination and independence in sparse graphs
    2026/07/24 by Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
    #cs.DS
  34. Fatness and Flatness
    2026/07/23 by Arnold Filtser, Hung Le, Nikolas Mählmann +2
    #math.CO #cs.DM #cs.DS #math.MG