Upper bounds and approximation results for the k-slow burning problem

DOI10.1016/J.DAM.2024.11.025MaRDI QIDQ6671389zbMATH OpenFDO

Authors Michaela Hiller, Arie M. C. A. Koster, Philipp Pabst

Publication date 27 January 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.11.025

zbMATH Keywords

approximation algorithmsbroadcastingburning numbercomputational complexity

Mathematics Subject Classification ID

Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Games involving graphs (91A43) Social networks; opinion dynamics (91D30)

Recommendations

• APX-hardness and approximation for the \(k\)-burning number problem
• APX-hardness and approximation for the \(k\)-burning number problem
• Burning a graph is hard
• Bounds on the burning numbers of spiders and path-forests
• Graph burning: tight bounds on the burning numbers of path forests and spiders

Cites work

• A linear algorithm for finding the k‐broadcast center of a tree
• A survey of gossiping and broadcasting in communication networks
• A survey of graph burning
• APX-hardness and approximation for the \(k\)-burning number problem
• Bounds on the burning numbers of spiders and path-forests
• Broadcasting in Trees with Multiple Originators
• Burning a graph as a model of social contagion
• Burning a graph is hard
• Information Dissemination in Trees
• Minimum broadcast graphs
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• On the burning number of \(p\)-caterpillars
• Some minimum broadcast graphs
• The burning number conjecture holds asymptotically

Cited in

(2)

• APX-hardness and approximation for the \(k\)-burning number problem
• APX-hardness and approximation for the \(k\)-burning number problem

This page was built for publication: Upper bounds and approximation results for the \(k\)-slow burning problem

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