Charles Explorer logo
🇨🇿

Graph Burning and Non-uniform k-Centers for Small Treewidth

Publikace na Matematicko-fyzikální fakulta |
2022

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

We study the graph burning problem and give a polynomial-time approximation scheme (PTAS) for arbitrary graphs of constant treewidth. This significantly extends the previous results, as a PTAS was known only for disjoint union of paths.

As a building block, we give an algorithm that proves the non-uniform k-center problem to be in XP when parameterized by the number of different radii and the treewidth of the graph. This extends the known exactly solvable cases of the non-uniform k-center problem; in particular this also solves the k-center with outliers on graphs of small treewidth exactly.