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

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455705" target="_blank" >RIV/00216208:11320/22:10455705 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-031-18367-6_2" target="_blank" >https://doi.org/10.1007/978-3-031-18367-6_2</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-18367-6_2" target="_blank" >10.1007/978-3-031-18367-6_2</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Graph Burning and Non-uniform k-Centers for Small Treewidth
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Graph Burning and Non-uniform k-Centers for Small Treewidth
Popis výsledku anglicky
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.

Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt
<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)