Algorithm Research On Connected Liar's Domination Sets In Graphs

With the development of network communication technology,wireless network is widely used in medical health,battlefield monitoring,agriculture and traffic control because of its advantages of easy installation,good flexibility and low cost.The nodes in the wireless communication network are all inexpensive sensors,each sensor is powered by the battery,and it has a life span.In order to increase the life cycle of wireless network monitoring and prevent the occurrence of information redundancy and broadcast storm,many experts and scholars have proposed to change the original information flood mode,using the virtual backbone network as the network base station of the wireless network,that is the connected dominating set.When a wireless network appears an intruder node,such as a fault point,a ignition point or a destructive node and so on.And the neighbor node of the intrusion node may fail,which may transmit the wrong information or not transmit any information.In this case,we require a certain fault tolerance of the virtual backbone.Slater proposed a false alarm fault-tolerant dominating set(LR)to enhance the fault tolerance of the network.In this paper,we mainly propose a algorithm of the minimum connected liar's dominating set in general connected graph(the number of vertices is more than 3).The corresponding polynomial model algorithm,the approximation algorithm,the precise algorithm and the heuristic algorithm are given in turn.Finally,the simulation and comparison of the precise algorithm and the heuristic algorithm are carried out.The details are as follows.Firstly,we prove the minimum connected liar's dominating set problem is the NP-hard problem and give the polynomial calculation model of LR and the polynomial model algorithm of CLR.we verify the minimum connected liar's dominating sets problem is NP-hard based on the complexity of the polynomial model algorithm.Secondly,we propose a approximation algorithm for connected liar's dominating set in general graphs.The approximate algorithm is based on greedy strategy,and its approximation ratio is 2(1 + ln ?).? is the maximum degree of graphs.The approximation ratio is better than previous approximation algorithms.Finally,we propose an exact algorithm and a polynomial time heuristic algorithm for solving the minimum connecting liar's dominating set problem.And we compare the result of two algorithms by computer simulation.