Graph burning and non-uniform k-centers for small treewidth

DOI10.1007/978-3-031-18367-6_2MaRDI QIDQ6176547zbMATH OpenOpenAlexFDO

Authors Matej Lieskovský, Jiří Sgall

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

\(k\)-center problemapproximation algorithmsgraph algorithmsPTAS

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(5)

• Orientable burning number of graphs
• Burning path-like and clique-like graphs
• Burn and win
• Orientable burning number of graphs
• Deterministic approximation algorithm for graph burning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176547)