APX-Hardness and Approximation for the k-Burning Number Problem
In: WALCOM: Algorithms and Computation ISBN: 9783030682101 WALCOM; (2021)
Online
unknown
Zugriff:
Consider an information diffusion process on a graph G that starts with \(k>0\) burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps \(b_k(G)\) such that all the vertices can be burned within \(b_k(G)\) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k.
Titel: |
APX-Hardness and Approximation for the k-Burning Number Problem
|
---|---|
Autor/in / Beteiligte Person: | Mondal, Debajyoti ; Kavitha, Veeraruna ; Rajasingh, Indra ; Parthiban, N. |
Link: | |
Quelle: | WALCOM: Algorithms and Computation ISBN: 9783030682101 WALCOM; (2021) |
Veröffentlichung: | Springer International Publishing, 2021 |
Medientyp: | unknown |
ISBN: | 978-3-030-68210-1 (print) |
DOI: | 10.1007/978-3-030-68211-8_22 |
Schlagwort: |
|
Sonstiges: |
|