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

DOI10.1016/j.tcs.2022.08.001OpenAlexW3037831187WikidataQ114129045 ScholiaQ114129045MaRDI QIDQ5918792

Angelin Jemima Rajasingh, N. Parthiban, Debajyoti Mondal, Indra Rajasingh

Publication date: 16 September 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.08.001

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Improved and generalized algorithms for burning a planar point set

Cites Work

• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• Some APX-completeness results for cubic graphs
• Bounds on the burning number
• 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 numbers of path forests and spiders
• On the burning number of \(p\)-caterpillars
• 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 spiders
• Graph burning: tight bounds on the burning numbers of path forests and spiders
• Burning a Graph as a Model of Social Contagion
• A survey of graph burning
• The Burning Number of Directed Graphs: Bounds and Computational Complexity
• How to Burn a Graph
• APX-hardness and approximation for the \(k\)-burning number problem
• Unnamed Item
• Unnamed Item

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