# Heuristics for Spreading Alarm throughout a Network
## 3 The Proposed Algorithms to Obtain the Shortest Burning Sequence
### Cutting Corners Heuristic  
Firstly, how to characterize a \"corner\" node? In the path graph in Figure 2, it would be a node of the degree 1, i.e., one of the end nodes. However, no such node exists, e.g., in a square lattice graph. We could select the nodes with smallest degree, but in networks corresponding to a tree graph there may be too many such nodes. Therefore, we chose to select the nodes with the lowest eigenvalues as the \"corner\" nodes. If we want to do a local optimization, we should not choose just one such \"corner\" node, but more, so that we would have a larger selection of \"central\" nodes within the graph distance \(bg-i\) from then. The number was set to \(\lceil\surd(|V(G)|S|i)\rceil\). This means a ceiling of a square root of the number of vertices would remain unburned if the current partial sequence \(\mathbf{X}\) was in time steps burned and spread the burns up to \(bg\) time steps (in the last steps, the new nodes not defined in \(\mathbf{X}\) yet would not be burned). Still, this characterization of \"corner\" nodes is not satisfactory. Let us take as an example a graph in Figure 3. If we take nodes with minimum eigenvalues, they are all positioned in the \"tail\", while we would prefer one node at the end of the tail and the rest in the corners of the square. Figure 3: Potential “corner” nodes with minimum eigenvalues are marked by a green color. However, we would prefer potential “corner” nodes also in the corners of the square, not only in the “tail”. Figure 2: Time steps of the burning a path on nine nodes: (**a**) Ideal case; (**b**) Result of the Algorithm 1. This problem has been solved by a sequential selection of the \"corner\" nodes, when the first one has the minimum eigenvalue, but the next one is one with the minimum eigenvalue of those nodes, which are at least a given minimum distance from any of the already selected nodes. The function _minDist(v,CornerNodes)_ finds the smallest graph distance of \(v\) to any of the nodes from the set of _CornerNodes_. This minimum distance was set to a floor of a half of average path length of the unburned remaining graph, after the partial sequence \(X\) would burn and spread the burns up to _bg_ time steps. For the selected \"corner\" nodes, the goal is to find the best \"center\" node ideally in the distance \(bg-i\) from the selected corner node. For each \"corner\" node, a maximum of three potential \"center\" nodes in the distance \(bg-i\) from the current \"corner\" node and with maximum eigenvalue in the graph with unburned vertices are selected. For each node from this this set of potential central nodes, the number \(ubn\) (unburned neighborhood) of unburned nodes in its \(bg-i\) neighborhood is evaluated, and nodes with the top quartile of the number of neighboring unburned nodes are selected. These nodes are then evaluated by the _apl_ (average path length) of the remaining unburned graph and by the number of its components, if their neighborhood would be burned. We then use a weighted aggregated sum product assessment (WASPAS) method to assess the quality of these central nodes. These nodes should have a maximum sized unburned neighborhood \(ubn\) (which they would cause to burn in the remaining time steps), a minimum average path length \(apl\) of the remaining unburned graph afterwards (more compact graphs burn better than linear paths) and the smallest possible number of the components _compNo_ of the remaining unburned graph. We used practically equal weights \(w\) for the normalized values of these parameters, but in general, different weights should be used for different types of graphs. The \(cb\) sequence contains \(max\), if the component is benefit, like \(ubn\), but \(cb\) contains \(min\), if the component is cost, like \(apl\) and \(compNo\). The best \"central\" node according to the WASPAS method was then added to the \(X\) sequence of nodes to burn.