Graph burning and non-uniform \(k\)-centers for small treewidth

DOI10.1007/978-3-031-18367-6_2OpenAlexW4312726025MaRDI QIDQ6176547

Jiří Sgall, Matej Lieskovský

Publication date: 25 July 2023

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-18367-6_2

zbMATH Keywords

graph algorithmsapproximation algorithmsPTAS\(k\)-center problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Parameterized complexity of graph burning
• Approximation algorithms for graph burning
• Burning a graph is hard
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Easy problems for tree-decomposable graphs
• A Best Possible Heuristic for the k-Center Problem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• How to Burn a Graph
• The Non-Uniform k -Center Problem

This page was built for publication: Graph burning and non-uniform \(k\)-centers for small treewidth