# Heuristics for Spreading Alarm throughout a Network
## 3 The Proposed Algorithms to Obtain the Shortest Burning Sequence
### Cutting Corners Heuristic
The Algorithm 2 can find an ideal burning sequence both for a path graph as well as for the artificial test example presented in Figure 1. However, from the NP complexity of the problem, it is clear, that there is still space for improvement. The simplest approach would be to search more candidate nodes to burn. ```
1:A network \(\mathbf{G}=(\boldsymbol{V},\boldsymbol{E})\) and a guess value \(bg\) of a burning number
2:A sequence \(\boldsymbol{X}\)= \(x_{1}\),..., \(x_{bg}\) of nodes from \(\boldsymbol{G}\)
3:\(\boldsymbol{X}\)\(\leftarrow\)0; \(\mathbf{TG}\)\(\leftarrow\)\(\boldsymbol{G}\); \(\boldsymbol{S}_{0}\)\(\leftarrow\)\(\boldsymbol{O}\);
4:for\(i=1,\,\ldots,\,b\)do
5:\(\boldsymbol{maxSizeComp}\)\(\leftarrow\) component of \(\mathbf{TG}\) with maximum number of nodes
6:if\(i\geq\) radius of maxSizeComponent
7:then\(x_{i}\)\(\leftarrow\)\(v\)\(\in\)\(\|\min\limits_{v\in(\boldsymbol{maxSizeComp})\setminus X}eccentricity(v,\boldsymbol{maxSizeComp})\|\)
8:else\(CentralNodes\)\(\leftarrow\)\(\boldsymbol{O}\);
9:\(\boldsymbol{CornerNodes}\)\(\leftarrow\)\(v\)\(\|\min\limits_{v\in V(\boldsymbol{maxSizeComp})}eigen\_centrality(v,\boldsymbol{maxSizeComp})\);
10:for\(j=2,\,\ldots,\,\big{\lceil}\sqrt{|\boldsymbol{V}(\boldsymbol{G})| \boldsymbol{S}_{i-1}|}\big{\|}\)do
11:\(\boldsymbol{minCornerDist}\)\(\leftarrow\)\(\boldsymbol{average.path.length}(\boldsymbol{maxSizeComponent})/2\)
12:\(\boldsymbol{distNodes}\)\(\leftarrow\)\(\{v\in V(\boldsymbol{maxSizeComp})|minDist(v,\boldsymbol{CornerNodes})\geq minCornerDist\}\)
13:\(\boldsymbol{CornerNodes}\)\(\leftarrow\)\(\boldsymbol{CornerNodes}\)\(\cup\)\(v\)\(\|\min\limits_{v\in\boldsymbol{distNodes}}eigen\_centrality(v,\mathbf{TG})\);
14:for\(k=1,\,\ldots,\,|\boldsymbol{CornerNodes}|\)do
15:\(\boldsymbol{tempNodes}\)\(\leftarrow\)\(\{v\in V(\boldsymbol{maxSizeComp})|dist(v,\boldsymbol{CornerNodes}_{i})\geq bg-i\}\)
16:\(\boldsymbol{tempNodes}\)\(\leftarrow\)\(decreasing\_order(eigen\_centrality(v,\boldsymbol{maxSizeComponent}),\,\,3\,\,nodes)\)\(\triangleright\)\(\boldsymbol{tempNodes}\)
17:\(\boldsymbol{CentralNodes}\)\(\leftarrow\)\(\boldsymbol{CentralNodes}\)\(\cup\)\(\boldsymbol{tempNodes}\)
18:for\(m=1,\,\ldots,\,|\boldsymbol{CentralNodes}|\)do
19:\(\boldsymbol{V}_{\epsilon}(\boldsymbol{CentralNodes}_{m})\)\(\leftarrow\)\(\mathrm{ego}(\boldsymbol{G},\,\,bg-i,\,\boldsymbol{CentralNodes}_{m})\);
20:\(\boldsymbol{ubn}\)\(=\)\(\mathrm{top}\)\(\boldsymbol{\mathrm{quartile}}\) values of \(\,\,\boldsymbol{ubn}\)
21:for\(r=1,\,\ldots,\,|\boldsymbol{CentralNodes}|\)do
22:\(\boldsymbol{\mathrm{ap}}_{r}\)\(\leftarrow\)\(\mathrm{average\_path.length}(G(\boldsymbol{V},\boldsymbol{E}(\mathbf{TG})\backslash\boldsymbol{E}(\boldsymbol{G}[S_{i}\cup \boldsymbol{V}(\boldsymbol{CentralNodes}_{r})]))\);
23:\(\boldsymbol{compN}_{\sigma}\)\(\leftarrow\)\(\mathrm{number\_of\_components}(G(\boldsymbol{V},\boldsymbol{E}(\mathbf{TG})\backslash\boldsymbol{E}(\boldsymbol{G}[S_{i}\cup \boldsymbol{V}(\boldsymbol{CentralNodes}_{r})]))\);
24:\(\boldsymbol{w}\)\(\leftarrow\)\((0.33,0.33,0.34)\)
25:\(\boldsymbol{lambda}\)\(\leftarrow\)\(0.5\)
26:\(\boldsymbol{cb}\)\(=\)\((\)max\_min\(,\)min\()\)
27:\(x_{i}\)\(\leftarrow\)best node determined by WASPAS(\(\boldsymbol{ubn}\),\(\boldsymbol{\mathrm{apl}}\),\(\boldsymbol{\mathrm{compNo}}\),\(\boldsymbol{w}\),\(\boldsymbol{\mathrm{cb}}\),\(\boldsymbol{\mathrm{lambda}}\));
28:\(\boldsymbol{X}\)\(\leftarrow\)\(X\cup x_{i}\)
29:\(\boldsymbol{S}_{i}\)\(\leftarrow\)\(\bigcup_{j=1}^{j-1}\boldsymbol{V}_{\sigma}\)\(\left\{x_{j}\right\}\);
30:\(\boldsymbol{E}(\mathbf{TG})\)\(\leftarrow\)\(\boldsymbol{E}(\mathbf{TG})\backslash\boldsymbol{E}(G[\boldsymbol{S}_{i}])\);
31:if\(\boldsymbol{S}_{i}\)\(\equiv\)\(\boldsymbol{V}\)then return \(\boldsymbol{X}\) else return FAILED TO BURN
```  
**Algorithm 2** Cutting corners heuristic for a shortest burning sequence