Multiple Intruder Locating Dominating Sets in Graphs: An Algorithmic Approach - Venugopal, K.; Vidya, K. A. (Communications in Mathematics and Applications, 2020)
A set \(SV\) of vertices (called codewords) of a graph \(G=(V, E)\) is called a Multiple Intruder Locating Dominating set (MILD set) if every non-codeword \(v\) is adjacent to at least one codeword \(u\) which is not adjacent to any other non-codeword. This enables one to locate intruders at multiple locations of a network and hence the name. The \(MILD(G)\) is the minimum cardinality of a \(MILD\) set in \(G\). Here, we show that the problem of finding MILD set for general graphs is NP-Complete. Further, we provide a linear time algorithm to find the MILD number of trees through dynamic programming approach and then, we extend the algorithm for unicyclic graphs.