16 citations · 188 across the 122 of their papers we have counts for
8 papers · 1 filter
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Graphs of bounded cliquewidth are polynomially -bounded
Marthe Bonamy, Michał Pilipczuk
We prove that if is a hereditary class of graphs that is polynomially -bounded, then the class of graphs that admit decompositions into pieces belonging to $\mathc…
Shorter Labeling Schemes for Planar Graphs
Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk
An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph from the class, assigns bit strings (labels) to vertices of so that for…
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk +1
In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this c…
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk
We consider the -Median problem on planar graphs: given an edge-weighted planar graph , a set of clients , a set of facilities , and an in…
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk
We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph , a set of clients , a set…
Reachability for Bounded Branching VASS
Filip Mazowiecki, Michał Pilipczuk
In this paper we consider the reachability problem for bounded branching VASS. Bounded VASS are a variant of the classic VASS model where all values in all configurations are upper…
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk +1
A hole in a graph is an induced cycle of length at least , and an antihole is the complement of an induced cycle of length at least . A hole or antihole is long if its length…