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

DOI10.1007/978-3-030-68211-8_22OpenAlexW3134117472MaRDI QIDQ5919106

No author found.

Publication date: 4 October 2021

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.14733

zbMATH Keywords

approximationnetwork analysisAPX-hardburning number\(k\)-burning

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (5)

Parameterized complexity of graph burning ⋮ Burning and \(w\)-burning of geometric graphs ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ Burning numbers of \(t\)-unicyclic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• On the burning number of generalized Petersen graphs
• Some APX-completeness results for cubic graphs
• Burning number of graph products
• The firefighter problem with more than one firefighter on trees
• An upper bound on the burning number of graphs
• Burning the plane. Densities of the infinite Cartesian grid
• Burning number of theta graphs
• Parameterized algorithms for Graph Burning problem
• Approximation algorithms for graph burning
• Bounds on the burning numbers of spiders and path-forests
• Burning a graph is hard
• Approximability of the firefighter problem. Computing cuts over time
• Burning a Graph as a Model of Social Contagion
• How to Burn a Graph
• APX-hardness and approximation for the \(k\)-burning number problem

This page was built for publication: APX-hardness and approximation for the \(k\)-burning number problem