13 citations · 27 across the 20 of their papers we have counts for
11 papers · 1 filter
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski
The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski
The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph is the minimum indep…
Tree decompositions with bounded independence number: beyond independent sets
Martin Milanič, Paweł Rzążewski
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-in…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Faster 3-coloring of small-diameter graphs
Michał Dębski, Marta Piecyk, Paweł Rzążewski
We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for -vertex diameter-2 graphs this problem can be solved in su…