Research On Algorithems For The S-Path Vertex Cover Problem

Each node in a computer network performs a number of traditional tasks: generating messages, routing and forwarding messages, consuming messages, and so on. But, some nodes in the network are also designated to perform additional tasks: collecting and analyzing statistics concerning the message traffic in the network and filtering the message traffic and discarding any detected attack message from it. We refer to those nodes that are designated to perform these additional tasks as network observers. If set all nodes as observer nodes in the network, it is not only a serious waste of network resources, but also it will increase the cost of building networks.So, how to select a smallest subset of nodes such that each message, that travels s(s≥2) nodes in network, is guaranteed to reach at least one node in the smallest subset is that need to solve. Combined with the secure communications problem of wireless sensor networks, s-path vertex cover problem is proposed. In addition, s-path vertex cover problem can be used in constructing optimal connectivity paths in wireless sensor networks; placement of monitoring equipment in different networks and so on.S-path vertex cover problem is that given a undirected graph and a positive integer s, find out one of a smallest subset of vertices from the graph such that every path of order s in the undirected graph contains at least one vertex which be part of the subset of vertices. And this problem has been proved to be NP-complete.In the paper, we will use parametric computing technology to designe exact algorithm on solving the s-path vertex cover problem. Our work as follows:First, give an optimal algorithm for s-path vertex cover problem in trees.Second, we use depth bounded search tree method to design exact algorithm of3-path vertex cover problem, and get an improvement algorithm which time complexity is O*(2.3028k) after a series of improvementsThird, we use depth bounded search tree method to design a exact algorithm of4-path vertex cover problem, and get an improvement algorithm which time complexity is O*(3.0122k) after a series of improvements.